1005 Seq (找规律)
Time Limit: 2000/1000 MS (Java/Others)
Memory Limit: 32768/32768 K (Java/Others)
Problem Description
度度熊有一个递推式 其中a1=1。现给出 n,需要求 an。
Input
第一行输入一个整数 T,代表 T (1≤T≤100000组数据。接下 T 行,每行一个数字 n (1≤n≤10^12)。
Output
输出 T 行,每行一个整数表示答案。
Sample Input
5
1
2
3
4
5
Sample Output
1
1
0
3
0
题意分析:
给出n,求( a[1] * 1 + a[2] * 2 + …… + a[n-1]*(n-1) ) % n;
解题思路:
先打个表出来,依次代表n,n/6, a[n]。
发现这个每6个是一轮,第一次打表的时候,也是没有发现规律的,最后才加上了中间的n/6。
第一个数是n/2;
第二个数是1+(n/6)* 4;
第三个数是1+(n/6)* 3;
第四个数是(n/6);
第五个数是3+(n/6)*6;
第六个数是n/6。
只要求出对6取余是哪一个数,输出相应的公式即可。
代码:
#include <stdio.h>
int main()
{
int T;
long long n;
scanf("%d", &T);
while(T--)
{
scanf("%lld", &n);
long long t=n/6;
if(n%6==3 || n%6==5)
printf("%lld\n", t);
else if(n%6==0)
printf("%lld\n", n/2);
else if(n%6==1)
printf("%lld\n", 1+t*4);
else if(n%6==2)
printf("%lld\n", 1+t*3);
else if(n%6==4)
printf("%lld\n", 3+t*6);
}
return 0;
}