再接再厉

Number Sequence

--------------------------------------------------------------------------------

Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 1092 Accepted Submit: 307

--------------------------------------------------------------------------------

A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2...Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another.

For example, the first 80 digits of the sequence are as follows:

11212312341234512345612345671234567812345678912345678910123456789101112345678910

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 <= i <= 2147483647)

Output

There should be one output line per test case containing the digit located in the position i.

Sample Input

2
8
3

Sample Output

2
2

/*解释一下:给定一个有规律的序列,它的每一个元素是由一位数字组成的,对输入一数,代表某元素在这个序列中的位置,输出这个元素,大家注意一下,10,11等等是拆开成2(3,4...)个数字的,也就占了两个位置.*/

2^x mod n = 1

--------------------------------------------------------------------------------

Time limit: 1 Seconds Memory limit: 32768K
Total Submit: 4209 Accepted Submit: 1144

--------------------------------------------------------------------------------

Give a number n, find the minimum x that satisfies 2^x mod n = 1.

Input

One positive integer on each line, the value of n.

Output

If the minimum x exists, print a line with 2^x mod n = 1.

Print 2^? mod n = 1 otherwise.

You should replace x and n with specific numbers.

Sample Input

2
5

Sample Output

2^? mod 2 = 1
2^4 mod 5 = 1

/*找出满足2^x mod n==1的最小x,如果找不到,则输出时用?代替.*/

第一个没这么简单吧

输入的数可以很大,但输出的数只有0 1 2 3 4 5 6 7 8 9 中的一个.

数据用long吧

[此贴子已经被作者于2006-12-10 20:58:15编辑过]

12
2^? mod 12 = 1
234
2^? mod 234 = 1
21
2^6 mod 21 = 1
223
2^37 mod 223 = 1
2345
2^132 mod 2345 = 1
23457
2^1116 mod 23457 = 1
1234567
2^5670 mod 1234567 = 1
1234321
2^111100 mod 1234321 = 1
19876765
2^1987676 mod 19876765 = 1
129826321
2^32456580 mod 129826321 = 1

浙江大学ACM里的.

第一个我还没做出来,想看看大家有什么高招.郁闷着...
大家帮忙啊

我的想法是把每一个数对应有多少个数字保存起来.并且有下面的递推式:


a[i]=a[i-1]+i的位数.i!=0
a[i]=0; i==0
与此同时做while(num>a[i])num-=a[i];一次循环可以出来.
则循环退出时,num必定在某个a[i]范围内.此时我只要将从1到i所有的数字求出来b[j](j从1开始保存),我就知道num对应的数字了.
是b[num];

不知道这样的想法是否正确...

1 2 3 4 ...9 10 11 12...
1 2 3 4 ...9 11 13 15...

实现过了,WA.
觉得想法应该没有错.

我的10是拆成两个数啊,要不然也不会是11了.