题意
给你一个序列,问你有多少个子序列它们的最大公约数为1
思路
- 先求出这些数中有多少个数含因子i
- 公约数为i的序列数为
代码
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp(aa,bb) make_pair(aa,bb) #define _for(i,b) for(int i=(0);i<(b);i++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define per(i,b,a) for(int i=(b);i>=(a);i--) #define mst(abc,bca) memset(abc,bca,sizeof abc) #define X first #define Y second #define lowbit(a) (a&(-a)) #define debug(a) cout<<#a<<":"<<a<<"\n" typedef long long ll; typedef pair<int,int> pii; typedef unsigned long long ull; typedef long double ld; const int N=100010; const int INF=0x3f3f3f3f; const int mod=1e9+7; const double eps=1e-6; const double PI=acos(-1.0); ll cnt[N];//cnt[i]表示含因子i的个数 ll power2[N];//2^n ll f[N];//f[i]表示公约数为i的序列数 void solve(){ int n;cin>>n; power2[0]=1; rep(i,1,n){ power2[i]=power2[i-1]*2%mod; int x;cin>>x; for(int j=1;j*j<=x;j++){ if(x%j==0){ cnt[j]++; if(j*j==x) continue; cnt[x/j]++; } } } for(int i=1;i<=1e5;i++) f[i]=(power2[cnt[i]]-1)%mod; for(int i=1e5;i>=1;i--){ for(int j=i+i;j<=1e5;j+=i){ f[i]=(f[i]-f[j]+mod)%mod; } } cout<<f[1]<<"\n"; } int main(){ ios::sync_with_stdio(0);cin.tie(0); // int t;cin>>t;while(t--) solve(); return 0; }