题目大意:
给你一个序列An,然后求有多少个序列Bn
满足Bi<=Ai,且这个序列的gcd不为1
题解:
考虑这样做
枚举一个因子k,然后求出有多少个序列的gcd包含这个因子k
然后把结果容斥一下,我们会发现,这个容斥恰好就是求莫比乌斯函数
所以直接先预处理出来即可
于是k从2到n依次枚举,然后把结果乘以u(k)加到最后的答案里。
另一个问题是,如何快速求出有多少个序列呢,如果单纯的把每个数除以k然后加起来,就是n^2logn
显然会超时。
所以这里先把数存起来,然后整体来做
对于k来说,每次就枚举k,2k,3k.....m*k,然后可以得到,能包含k的数有多少个,2k的数有多少个,那么我们就可以在n/k的复杂度下统计出来有多少个序列
然后枚举k,最后就是n+n/2+...n/k = nlogn的复杂度了
(可能有更好的做法)
#include#include #include #include using namespace std;const int maxn = 1e5 + 100;const int MOD = 1000000007;typedef long long LL;LL minpri[maxn], H[maxn], a[maxn], ans[maxn], flag[maxn];vector prime;const int maxlen=maxn;int mu[maxlen],prinum[maxlen], len=0;void CalPri(){ int num[maxlen]; for(int i=2;i >= 1){ if(b&1) (ANS *= a) %= MOD; (a *= a) %= MOD; } return ANS;}int main(){ int T, n; cin>>T; Calmu(); for(int ncase = 1; ncase <= T; ncase++){ scanf("%d", &n); memset(H, 0, sizeof(H)); memset(ans, 0, sizeof(ans)); LL ANS = 0, Max = 0, Min = 1e9; for(int i = 1; i <= n; i++) scanf("%d", &a[i]), H[a[i]]++, Max = max(Max, a[i]), Min = min(Min, a[i]); for(int i = Max; i >= 0; i--) H[i] += H[i+1]; //for(int i = 1; i <= Max; i++) cout< <<" "; cout< 0 ? 1 : 0; for(int i = 2; i <= tot; i++) (temp *= mypow(i, ans[i])) %= MOD; (ANS += temp*(-mu[x])) %= MOD; for(int i = 1; i <= tot; i++) ans[i] = 0; } (ANS += MOD) %= MOD; cout<<"Case #"< <<": "< <