2017 Multi-University Training Contest

TrickGCD

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 2097 Accepted Submission(s): 816

Sample Input

1

4

4 4 4 4

Sample Output

Case #1: 17

Source

2017 Multi-University Training Contest - Team 2

最近不舒服病了找个时间来解释

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cstdlib>
 6 #include<string.h>
 7 #include<set>
 8 #include<vector>
 9 #include<queue>
10 #include<stack>
11 #include<map>
12 #include<cmath>
13 typedef long long ll;
14 typedef unsigned long long LL;
15 using namespace std;
16 const double PI=acos(-1.0);
17 const double eps=0.0000000001;
18 const int N=200000+100;
19 const int mod=1e9+7;
20 const int INF=0x3f3f3f3f;
21 int num[N],mo[N];
22 void mobius(){
23     mo[1]=1;
24     for(int i=1;i<=N;i++)
25     for(int j=i+i;j<=N;j+=i)
26     mo[j]-=mo[i];
27 }
28 int pow_mod(int a,int b){
29     ll ans=1;
30     while(b)
31     {
32         if(b&1)ans=(ans*a)%mod;
33         a=(1ll*a*a)%mod;
34         b>>=1;
35     }
36     return ans;
37 }
38 int main(){
39     int t,n,x,minn,kase=0;
40     mobius();
41     scanf("%d",&t);
42     while(t--)
43     {
44         memset(num,0,sizeof(num));
45         for(int i=1;i<=N;i++){
46             num[i]=num[i-1]+num[i];
47         }
48         minn=INF;
49         scanf("%d",&n);
50         for(int i=1;i<=n;i++){
51             scanf("%d",&x);
52             minn=min(minn,x);
53             num[x]++;
54         }
55         ll ans=0;
56         for(int i=2;i<=minn;i++)
57         {
58             int cnt=1;
59             for(int j=1;j*i<=100000;j++)
60             {
61                 cnt=(1(ll)*cnt*pow_mod(j,num[i*(j+1)-1]-num[i*j-1]))%mod;
62             }
63             ans=(ans-1(ll)*mo[i]*cnt+mod)%mod;
64         }
65         printf("Case #%d: %lld
",++kase,ans);
66     }
67     return 0;
68 }