ZOJ 2674 Strange Limit

ZOJ2674 Strange Limit

source code (ZOJ2674.c) [recursion, number theory, Euler's theorem]

求a ^a..a%m!的极限。

欧拉定理的内容是：如果a和n互质，那么a^φ(n)=1(mod n)；对于任意a, n和较大的b>= φ(n) ，有a^b=a^{φ(n)+b mod φ(n)}(mod n)。 证明

于是利用欧拉定理，问题就很简单了，我们把上面问题的极限记为x=gao(a, b=m!)。那么假设y=gao(a, φ(b))，就有x=a^φ(b)+ymod b，而如果b=1，显然x=0。

#include <iostream>
#include <cstring>
#include <cstdio>using namespace std;typedef long long ll;ll gcd(ll a, ll b) { return b==0 ? a: gcd(b, a%b); }ll fac[45];
ll p[345] = {2, 3, 5, 7, 11, 13, 17, 23};ll powmod(ll a, ll b, ll m)
{ll ret = 1;for(;b;b>>=1, a=a*a%m) if(b&1) ret = ret*a % m;return ret;
}
ll phi(ll n)
{ll ret = 1;for(int i=0;n>1;i++){if(n%p[i]) continue;ret *= p[i] - 1;n /= p[i];while(n%p[i]==0){ret *= p[i];n /= p[i];}}return ret;
}
ll gao( ll a, ll b)
{if(b==1) return 0;ll d = phi(b);return powmod(a, d+gao(a,d), b);
}
int main()
{fac[0] = 1;for(int i=1;i<33;i++) fac[i] = fac[i-1] * i;bool blank = false;ll a, b;while(scanf("%lld%lld", &a, &b)!=EOF){if(blank) putchar(10);blank = true;printf("%lld\n", gao(a, fac[b]));}
}