UVALive4998 Simple Encryption(数论 同余)

题意：

给出K1，求一个12位数（不含前导0）K2，使得K1^K2 mod (10^12) = K2

思路：借鉴他人思路，任取一个K2,若K1^K2 mod (10^12) != K2,则令K2 = K1^K2 mod (10^12) ，效率较高，但具体原因不知，若了解原因请指教

//http://www.cnblogs.com/IMGavin/
#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <set>
#include <bitset>
#include <algorithm>
using namespace std;

typedef long long LL;
#define gets(A) fgets(A, 1e8, stdin)
const int INF = 0x3F3F3F3F, N = 18, MOD = 1003;
LL p[N];
LL ans;
int n;

LL MultMod(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 PowMod(LL a,LL b,LL MOD){
	LL ret=1;
	while(b){
		if(b&1) ret=MultMod(ret,a,MOD);
		a=MultMod(a,a,MOD);
		b>>=1;
	}
	return ret;
}


LL solve(LL x){
	while(1){
		LL tp = PowMod(n, x, p[12]);
		if(tp != x){
			x = tp;
		}else{
			break;
		}
	}
	return x;
}

int main(){
	p[0] = 1;
	int cas = 0;
	for(int i = 1 ; i < N; i++){
		p[i] = p[i - 1] * 10ll;
	}
	
	while(cin >> n, n){
		printf("Case %d: Public Key = %d Private Key = %lld
", ++cas, n, solve(13));
	}

	return 0;
}