超大数取模 (Huge Mod,UVa 10692)

 1 #include <iostream>
 2 #include <string.h>
 3 #include <string>
 4 #include <fstream>
 5 #include <algorithm>
 6 #include <stdio.h>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <cmath>
11 using namespace std;
12 const double eps = 1e-8;
13 const double pi=acos(-1.0);
14 const int INF=0x7fffffff;
15 unsigned long long uINF = ~0LL;
16 #define MAXN 1007
17 typedef long long LL;
18 int phi[10010];
19 void phi_table()
20 {
21     for(int i=2;i<=10000;i++) phi[i]=0;
22     phi[1]=1;
23     for(int i=2;i<=10000;i++) if(!phi[i])
24        for(int j=i;j<=10000;j+=i)
25        {
26            if(!phi[j]) phi[j]=j;
27            phi[j]=phi[j]/i*(i-1);
28        }
29 }
30 int pow_mod(int a,int p,int n)
31 {
32     if(p==0)return 1;
33     int ans=pow_mod(a,p/2,n);
34     ans=ans*ans%n;
35     if(p%2==1)ans=ans*a%n;
36     return ans;
37 }
38 int n,m,a[11];
39 bool Read()
40 {
41     string s;
42     cin>>s;
43     if(s=="#")return false;
44     m=0;
45     for(int i=0;i<s.length();i++)
46     {
47         m=m*10+(s[i]-'0');
48     }
49     scanf("%d",&n);
50     for(int i=0;i<n;i++)
51     scanf("%d",&a[i]);
52     return true;
53 }
54 //a^x≡a^(x%phi(c)+phi(c))(mod c)
55 int dfs(int d,int mod)
56 {
57     if(d==n-1)return a[n-1]%mod;
58     int temp=dfs(d+1,phi[mod]);
59     int ans=pow_mod(a[d],temp+phi[mod],mod);
60     return ans;
61 }
62 int main()
63 {
64     int T=1;
65     //freopen("0.in","r",stdin);
66     phi_table();
67     while(Read())
68     {
69         printf("Case #%d: %d
",T++,dfs(0,m));
70     }
71 
72     return 0;
73 }

a^x≡a^(x%phi(c)+phi(c))(mod c)