拓展phi-容斥

数学# #模板#

先求质数，记得每个i无论是不是质数都要当筛子筛一次。

然后就是经典容斥。

#include<bits/stdc++.h>
#define ll long long
#define fd(i, a, b) for (ll i = a; i >= b; i--)
#define r(i, a) for (ll i = fir[a]; i; i = e[i].nex)
#define file(a) freopen(#a ".in", "r", stdin);
#define il inline
#define gc getchar()
#define f(i,a,b) for(ll i=a;i<=b;i++)
using namespace std;
const ll maxn=1e5+10,INF=1e16;
il ll read(){
    ll x=0,f=1;char ch=gc;
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc;}
    while(ch>='0'&&ch<='9') x=(x*10)+(ch^48),ch=gc;
    return x*f;
}
ll x,y,pre[maxn],cnt;
il ll dfs(ll a,ll b,ll s){
    if(!b){return y/s;}
    if(s>y) return 0;
    if(a>cnt) return 0;
    ll ret=dfs(a+1,b,s)+dfs(a+1,b-1,s*pre[a]);
    return ret;
}
ll zs[maxn],tot;
bool vis[maxn];
int main()
{
    x=read(),y=read();
    vis[1]=1;
    f(i,2,x){
        if(!vis[i]) zs[++tot]=i;
        for(ll j=1;j<=tot&&i*zs[j]<=x;j++){
            vis[i*zs[j]]=1;
            if((i%zs[j])==0) break;
        }
    }
    f(i,1,x){
        cnt=0;
        f(j,1,sqrt(i)){
            if((!(i%j))){
                if(!vis[j])pre[++cnt]=j;
                if(j!=i/j) if(!vis[i/j])pre[++cnt]=i/j;
            } 
        }
        // f(i,1,cnt) cout<<pre[i]<<" ";
        // cout<<endl;
        ll ans=0;
        f(i,1,cnt) ans+=(i&1)?dfs(1,i,1):-dfs(1,i,1);
        printf("%lld\n",y-ans);
    }
}