Codeforces-803 F-Coprime Subsequences(ふるい)

タイトルリンク:Codeforces-803 F-Coprime Subsequences
f(i)はiをgcdとするシーケンス数とし、初期化f(i)=2 c(i)−1、c(i)はiを因子とする数の個数とする.直接加算すると必ず重複する部分があるので、後から前へふるいf(i)=f(i)−Σi|df(d)すればよい.

#include
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int maxn=1e5+7;
ll p[maxn],f[maxn],ans;
int a[maxn],c[maxn],n,m,t;
int main()
{
    cin>>m;
    p[0]=1;
    for(int i=1;i<=m;i++) p[i]=p[i-1]*2%mod;
    for(int i=1;i<=m;i++) cin>>t,++a[t],n=max(n,t);
    for(int i=1;i<=n;i++)
    {
        int t=0;
        for(int j=i;j<=n;j+=i) t+=a[j];
        f[i]=p[t]-1;
    }
    for(int i=n;i;i--)
    {
        for(int j=i*2;j<=n;j+=i) f[i]=(f[i]-f[j]+mod)%mod;
        ans=(ans+t)%mod;
    }
    cout << f[1] << endl;
    return 0;
}