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就可以了.
沒明白這思路，代碼就不貼了。。