题意
输入正整数 $K_1$($K_1 \leq 50000$),找一个12为正整数 $K_2$(不能含有前导0)使得 ${K_1}^{K_2} \equiv K_2(mod \ {10}^{12})$。例如 $K_1=99$,$K_2=817 \ 245\ 479\ 899\ $.
分析
1、利用自相似性质
如果 ${K_1}^{K_2} \equiv K_2(mod \ {10}^{12})$,那么有 ${K_1}^{K_2 \% {10}^i} \equiv K_2\% {10}^i(mod \ {10}^{i}), \ i \leq 12$.
因此可以dfs从后往前一位一位得到。
考虑到不能含有前导0,可以求到13位,并要求大于等于1e12,答案再模1e12,这样就不会出现前导0.
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e12; ll K1, K2; ll w[15], ans; ll quickmul(ll a,ll b,ll mod) { ll ite = (1LL<<20)-1; return (a*(b>>20)%mod*(1ll<<20)%mod+a*(b&(ite))%mod)%mod; } ll qpow(ll a, ll b, ll mod) { ll ret = 1; while(b) { if(b&1) ret = quickmul(ret, a, mod); a = quickmul(a, a, mod); b >>= 1; } return ret; } bool dfs(int cur, ll now) { if(cur == 13) { if(now >= w[12]){ans = now; return true;} return false; } ll W = w[cur]; for(int i = 0;i <= 9;i++) { ll tmp = W*i + now; if(qpow(K1, tmp, W) == (tmp%W)) { if(dfs(cur+1, tmp)) return true; } } return false; } int main() { int kase = 0; w[0] = 1; for(int i = 1;i < 15;i++) w[i] = w[i-1] * 10; while(scanf("%lld", &K1) == 1 &&K1) { dfs(0, 0); printf("Case %d: Public Key = %lld Private Key = %lld\n", ++kase, K1, ans%mod); } }
2、不动点迭代
初始时随机选取一个超过10^12的数,如1000000000007,将其代入计算,如果f(x)!=x,那么令x=f(x),如此循环,能在短时间内找出合法解。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod = 1e12; ll K1, K2; ll quickmul(ll a,ll b,ll mod) { ll ite = (1LL<<20)-1; return (a*(b>>20)%mod*(1ll<<20)%mod+a*(b&(ite))%mod)%mod; } ll qpow(ll a, ll b, ll mod) { ll ret = 1; while(b) { if(b&1) ret = quickmul(ret, a, mod); a = quickmul(a, a, mod); b >>= 1; } return ret; } int main() { int kase = 0; while(scanf("%lld", &K1) == 1 &&K1) { K2 = 1e11+7; while(qpow(K1, K2, mod) != K2%mod) K2 = qpow(K1, K2, mod); printf("Case %d: Public Key = %lld Private Key = %lld\n", ++kase, K1, K2); } }
参考链接: