题目：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】
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Comparator;
import java.util.Scanner; public class Main {
static Scanner scan = new Scanner(System.in);
static BigInteger one[] = {BigInteger.valueOf(1), BigInteger.valueOf(1), BigInteger.valueOf(4), BigInteger.valueOf(4), BigInteger.valueOf(2),
BigInteger.valueOf(1), BigInteger.valueOf(1), BigInteger.valueOf(4), BigInteger.valueOf(4), BigInteger.valueOf(2)}; static BigInteger n;
static int k; static BigInteger quick_pow(BigInteger a, BigInteger b, BigInteger mod){
BigInteger res = BigInteger.ONE;
BigInteger tmp = a;
while(b.compareTo(BigInteger.ZERO) != 0){
if(b.mod(BigInteger.valueOf(2)).compareTo(BigInteger.valueOf(1)) == 0){
res = res.multiply(tmp).mod(mod);
}
tmp = tmp.multiply(tmp).mod(mod);
b = b.divide(BigInteger.valueOf(2));
}
return res;
} //求第k位的循环节
static BigInteger get(BigInteger a, BigInteger b, BigInteger mod){
BigInteger res = BigInteger.ONE;
BigInteger first = a;
while(true){
a = a.multiply(b).mod(mod);
if(a.compareTo(first) == 0)break;
res = res.add(BigInteger.ONE);
if(res.compareTo(BigInteger.valueOf(11)) == 0)return BigInteger.valueOf(-1);
}
return res;
} static public void main(String[] args){
//System.out.println(quick_pow(BigInteger.valueOf(2), BigInteger.valueOf(6), BigInteger.valueOf(100))); n = scan.nextBigInteger();
k = scan.nextInt(); BigInteger ans = BigInteger.ZERO;
BigInteger mod = BigInteger.valueOf(10);
for(int i = 0; i != k; i++, mod = mod.multiply(BigInteger.valueOf(10))){
BigInteger last = n.mod(mod);
if(ans.compareTo(BigInteger.ZERO) == 0){
ans = one[last.intValue()];
}else{
BigInteger tmp = last;
last = quick_pow(last, ans, mod).mod(mod);
ans = ans.multiply(get(tmp, last, mod));
if(ans.compareTo(BigInteger.valueOf(0)) < 0){
System.out.println(-1);
return;
}
}
} System.out.println(ans);
}
}