http://acm.hdu.edu.cn/showproblem.php?pid=2837
题意：求解 f(n)=(n%10)f(n/10)%m f ( n ) = ( n % 10 ) f ( n / 10 ) % m ，其中 (2<=n,m<=109) ( 2 <= n , m <= 10 9 )
看到指数取模，考虑指数循环节，公式如下：
ax≡ax%phi(m)+phi(m) (mod m) a x ≡ a x % p h i ( m ) + p h i ( m ) ( m o d m )
然后套这个公式递归求解即可，但有奇怪的边界问题，结果取模就炸，中间过程取模也要特殊判断(具体看代码)。
#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
#define ll long long
using namespace std;ll n,m;
int T;
ll qpow(ll a,ll b,ll mod)
{if(a==0) return b==0;ll res=1;while(b){if(b&1) res=(res*a)%mod;b>>=1;a=(a*a)%mod;}return res==0?mod:(res+mod)%mod;//因为这个WA了一上午
}ll phi(ll a)
{ll res=a,tmp=a;for(ll i=2;i*i<=tmp;i++){if(a%i==0){res=res/i*(i-1);while(a%i==0) a/=i;}}if(a>1) res=res/a*(a-1);return res;
}ll f(ll a,ll b)
{if(a==0) return 1;if(a<10) return a;return qpow((a%10),f(a/10,phi(b)),b);
}int main()
{scanf("%d",&T);while(T--){scanf("%lld%lld",&n,&m);printf("%lld\n",f(n,m));}return 0;
}