很水的一道题，数论做的很少。这题的输入是一个数列中的前三个数，然后根据输入判断是等差数列还是等比数列，然后求出第n项。囧，高中的公式就不写了～～
需要注意的地方是对结果取摸：A×B%M = ((A%M)*((B%M)%M)
最重要是求等比数列的时候： 求幂乘要用二分来乘，否则会TLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <stdlib.h>
#include <string.h>
#define M 200907
long long a1,a2,a3;
long long d,n,an;
long long (long long x,long long a,long long n)
{
int i;
for (i = 0; (1LL<<i)<=n;i++)
{
if(n&(1LL<<i))
x = x*a%M;
a = a*a%M;
}
return x;
}
int main()
{
freopen("Sample Input.txt","r",stdin);
long long T;
scanf ("%I64d",&T);
while (T--)
{
scanf("%I64d%I64d%I64d%I64d",&a1,&a2,&a3,&n);
if ( (a2-a1)==(a3-a2) )
{
d = a2-a1;
an = (((a1%M+((n-1)%M)*(d%M)))%M)%M;
}
else
{
d = a2/a1%M;
an = cal(a1%M,d,n-1)%M;
}
printf("%I64dn",an);
}
getch();
return 0;
}
|
近期评论