There are some short-cut ways to check divisibility of numbers in base 10. Here are some examples:
1.Remember divisibility testing of 3 in base 10? It was simple, right? We need to add all the digits and then check if it is divisible by 3. Call this method “1-sum”.
2.In case of testing of 11, we need to add all digits by alternating their signs. For example, 1354379988104 = 11*123125453464 and (4-0+1-8+8-9+9-7+3-4+5-3+1) = 0, which is divisible by 11 (0 = 0*11). Lets call this method “1-altersum”.
3.In case of 7, we need to add all 3-digit-groups by alternating their signs. For example, 8618727529993 = 7*1231246789999 and (993-529+727-618+8) = 581, which is divisible by 7 (581 = 7*83). Similarly, we call this method “3-altersum”.
4.In similar Manner, 13’s checking is “3-altersum”.
In this problem, we are interested to see divisibility checking of only prime numbers in base 10. For a prime P, you need to find the smallest positive integer N such that P’s divisibility testing is “N-sum” or “N-altersum”.
Input
At first you will be given T (T ≤ 1000), the number of test cases. Then T lines will follow. In each line there will be single integer P (P ≤ 231-1 = 2147483647), the prime number (P is a prime number NOT equal to 2 or 5).
Output
For each line of input, produce exactly one line of output like either “Case : -sum” or “Case : -altersum”. Please see sample input and output for details.
Sample
Input
4
3
7
11
13
Output
Case 1: 1-sum
Case 2: 3-altersum
Case 3: 1-altersum
Case 4: 3-altersum
题意： 自己看吧，怕是自己会错了题意，
写了接近几个小时都没写出来，看学长写得题解，也是很迷啊，怎么想到的。。
贴上学长写的思路。。。
题意:对于给定的素数, 找到最小的n满足p的” divisibility testing”为”N-sum”或”N-altersum”
分析:通过对题目中给N-sun, N-altersum的定义分析, 可以猜测, 当10^t % p == 1时, 答案为t-sum, 当10^t % p == p – 1时, 答案为t-altersum. 然后从小到大枚举t, 发现会TLE. 再看10^t % p这个式子, 发现根据费马小定理, 当t = p – 1时, 10^(p - 1) % p == 1 一定成立, 但t = p – 1却不是题目要求的最小值, 再打表发现, 最终结果都是p – 1的约数, 然后枚举一下p – 1的约数, 判断模p是否为1或p – 1就可以了.
没明白这思路，代码就不贴了。。