1005 Seq （找规律）

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;
}