HDU6053TrickGCD

题目连接

题意

​ 给定一个长为n的数组A，求解一定条件下能构造多少个不同数组B。条件为 1≤Bi≤Ai 和 对于任意的 l,r(1≤l≤r≤n) ， gcd(Bl,Bl+1,...,Br)≥2 .

分析

​ 显然gcd最小的情况必然是在 l=1,r=n 时取得，所以仅考虑 l=1,r=n 的情况即可。考虑枚举 gcd(B1,B2,...,Bn) 的结果。举例 gcd(B1,B2,...,Bn)=2 ， B1 对这个方案的种类贡献为 b1=B1/2 ，那么总方案数为 ∏ni=1bi ，容斥处理掉重复计算的结果即可。接下来问题是怎么快速求取 bi 。暴力尝试A数组的每个数显然时间上不可行。于是考虑枚举 bi=j ，查询存在几个数在这个范围内。赛时一直算不清复杂度，忘了这样处理的复杂度为 O(n×ln(n)) ,一直纠结于一个 O(n32) 的算法。

代码

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<cmath> #include<queue> using namespace std; const int N = 100000 + 10; const int mod = 1e9 + 7; int T, n, a[N], ca[N*2], inv[N] = {0, 1}, cnt[N], vis[N]; int mn, mx; long long quick_pow(long long a,long long b){ long long ret=1; while(b){ if(b&1) ret=(ret*a)%mod; b>>=1; a=(a*a)%mod; } return ret; } bool isSqr[N]; int lowbit(int x){ return x&-x; } void prime() { memset(isSqr, 0, sizeof(isSqr)); for(int i=2;i<=100000;i++) { if(cnt[i]) continue; for(int j=i;j<=100000;j+=i) { cnt[j]++; if(j % (i*i) == 0) isSqr[j] = 1; } } } int getnum(int k){ long long ret=1; for(int i=1;i<=100000;++i){ if(k*i>mx) break; int num=ca[k*(i+1)-1]-ca[k*i-1]; if(num==0) continue; ret*=quick_pow(i,num); if(ret>mod) ret%=mod; } return ret; } int main() { for(int i=2;i<N;i++) inv[i] = (mod - mod/i) *1ll* inv[mod%i] % mod; prime(); scanf("%d", &T); for(int ica=1;ica<=T;ica++) { scanf("%d", &n); memset(ca,0,sizeof(ca)); mn=100000,mx=0; for(int i=1;i<=n;i++) { scanf("%d", &a[i]); mn = min(mn, a[i]); mx = max(mx,a[i]); ca[a[i]]++; } if(mn == 1) { printf("Case #%d: 0\n", ica); continue; } for(int i=2;i<N*2;++i) ca[i]+=ca[i-1]; int ans = 0; int func = 1; for(int i=2;i<=mn;i++) { func=getnum(i); if(isSqr[i]) continue; if(cnt[i] % 2) ans += func; else ans -= func; ans%=mod; } ans=(ans+mod)%mod; printf("Case #%d: %d\n", ica, ans); } }