题意： 输入正整数K1(K1≤50000),找一个12位正整数K2（不能含有前导零）使得K1^K2≡K2(mod10^12)。
思路： 神奇的数论题，怎么也想不出来，膜膜大佬的方法。 K1^K2≡K2(mod10^12)，同时意味着： K1^K2≡K2(mod10^i),i ≤12 现在我们用（abcd）表示一个四位数，用（bcd）表示它的后三位； 对于任意一个底数k；我们要证明如果 k^(abcd) = abcd(mod 1e4); 就有 k^(bcd) = bcd(mod 1e3); 显然 k^(abcd) = bcd (mod 1e3) k^(abcd) = k^(a000) * k^(bcd) = bcd (mod 1e3) 并且根据欧拉函数的求法，有φ(10^i)=10^i*(1-1/2)*(1-1/5)=4*10^(i-1) 所以 φ(1e3) = 4*10^2 根据欧拉定理 k^ φ(1e3) = 1 (mod 1e3) 又因为 a000 是 φ(1e3) 的倍数; 所以 k^ (a000) = 1 (mod 1e3) 那么 k^(abcd) = k^(a000) * k^(bcd) = k^(bcd) = bcd (mod 1e3) 所以 如果 k^(abcd) = abcd(mod 1e4); 就有 k^(bcd) = bcd(mod 1e3); 同理，我们可以得到 如果 k^(abcd…) = abcd…(mod 1ei); 就有 k^(bcd…) = bcd…(mod 1ei-1); 那么我们反向思考，要去找这个12位的k2，就去找一个i位的k3满足 K1^k3≡k3(mod10^i)。 合法的k2就是在这个k3上加上一些前导。 所以就可以用dfs像数位dp这样搞啦！
#include <algorithm> #include <cstdio> #include <cstring> #include <iostream> #define LL long long using namespace std; LL multi(LL x, LL y, LL mod){//神奇的快速乘隔开后20位单独算 LL lf = x * (y >> 20) % mod * (1ll << 20) % mod; LL rg = x * (y & ((1ll << 20) - 1)) % mod; return (lf + rg) % mod; }//首先考虑模数最大为10^12，不超过2进制中的40位，那么我们可以将待乘值拆分成高20位与低20位， //确保在乘法时始终不超过60位. LL power(LL a, LL p, LL mod){ LL ans = 1; while( p ){ if(p & 1) ans = multi(ans, a, mod); p >>= 1; a = multi(a, a, mod); } return ans % mod; } LL n; LL ans[50010]; bool flag; void dfs(int pos, LL pre, LL mod){ if(pos == 12){ if(pre < 1e11 || power(n, pre, mod) != pre) return; ans[n] = pre; flag = 1; return; } for(int i=0; i<=9; i++){ LL nex = mod * i + pre;//k2 从个位开始推（加一个前导） LL lf = power(n, nex, mod);//左式 LL rg = nex % mod;//右式 if(lf != rg) continue; dfs(pos + 1, nex, mod * 10); if( flag ) return;//找到一个ans就返回 } } void solve(){ if(ans[n] != -1) return;//记忆化搜索 flag = 0; dfs(0, 0, 1); } int main(){ int kase = 0; memset(ans, -1, sizeof(ans)); while(~scanf("%lld", &n) && n){ solve(); printf("Case %d: Public Key = %lld Private Key = %lld\n", ++kase, n, ans[n]); } }