洛谷P1050 循环【java大数】

题目：https://www.luogu.org/problemnew/show/P1050

题意：给定一个数$n$，问$n$的幂次的最低$k$位的循环节是多少。

思路：这真是我做过最难的java大数了！！！！【我太菜了】

六月去清华的机试题之一，当时觉得好像很眼熟没做出来。拖延症患者今天终于参考着题解写完了，现在想想没做出来也能原谅自己了....

若循环节为$a_1$，那么其实需要同时满足最低1位循环，最低2位循环，最低3位循环.......

也就是说$a_1$应该是，最低的这$k$位循环的公倍数。

所以我们枚举位数，最后$i$位的循环节肯定是$i-1$循环节的倍数。

所以要先求一下最低$i$位的$ans$幂次，然后以这个为倍数去找是否出现循环。如果超过10还没有循环说明肯定不会循环了，因为数字只有0~9

【可能我自己也写得糊里糊涂的所以题解也写得糊里糊涂得dbq】

 1 import java.lang.reflect.Array;
 2 import java.math.BigInteger;
 3 import java.util.Arrays;
 4 import java.util.BitSet;
 5 import java.util.Comparator;
 6 import java.util.Scanner;
 7 
 8 public class Main {
 9     static Scanner scan = new Scanner(System.in);
10     static BigInteger one[] = {BigInteger.valueOf(1), BigInteger.valueOf(1), BigInteger.valueOf(4), BigInteger.valueOf(4), BigInteger.valueOf(2),
11             BigInteger.valueOf(1), BigInteger.valueOf(1), BigInteger.valueOf(4), BigInteger.valueOf(4), BigInteger.valueOf(2)};
12 
13     static BigInteger n;
14     static int k;
15 
16     static BigInteger quick_pow(BigInteger a, BigInteger b, BigInteger mod){
17         BigInteger res = BigInteger.ONE;
18         BigInteger tmp = a;
19         while(b.compareTo(BigInteger.ZERO) != 0){
20             if(b.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(1)) == 0){
21                 res = res.multiply(tmp).mod(mod);
22             }
23             tmp = tmp.multiply(tmp).mod(mod);
24             b = b.divide(BigInteger.valueOf(2));
25         }
26         return res;
27     }
28 
29     //求第k位的循环节
30     static BigInteger get(BigInteger a, BigInteger b, BigInteger mod){
31         BigInteger res = BigInteger.ONE;
32         BigInteger first = a;
33         while(true){
34             a = a.multiply(b).mod(mod);
35             if(a.compareTo(first) == 0)break;
36             res = res.add(BigInteger.ONE);
37             if(res.compareTo(BigInteger.valueOf(11)) == 0)return BigInteger.valueOf(-1);
38         }
39         return res;
40     }
41 
42 
43     static public void main(String[] args){
44         //System.out.println(quick_pow(BigInteger.valueOf(2), BigInteger.valueOf(6), BigInteger.valueOf(100)));
45 
46         n = scan.nextBigInteger();
47         k = scan.nextInt();
48 
49 
50         BigInteger ans = BigInteger.ZERO;
51         BigInteger mod = BigInteger.valueOf(10);
52         for(int i = 0; i != k; i++, mod = mod.multiply(BigInteger.valueOf(10))){
53             BigInteger last = n.mod(mod);
54             if(ans.compareTo(BigInteger.ZERO) == 0){
55                 ans = one[last.intValue()];
56             }else{
57                 BigInteger tmp = last;
58                 last = quick_pow(last, ans, mod).mod(mod);
59                 ans = ans.multiply(get(tmp, last, mod));
60                 if(ans.compareTo(BigInteger.valueOf(0)) < 0){
61                     System.out.println(-1);
62                     return;
63                 }
64             }
65         }
66 
67         System.out.println(ans);
68     }
69 }