题解 | #小y的质数#【小y的质数.题解】

【小y的质数.题解】

看题解代码冗杂，我是没有看懂，所以就按着他的大部分意思在加上自己 YY 的想法给搞出来了。

我们都知道，对于 是恒成立的，不会的同学自行百度吧，基础知识。那么我们最终可以将给出的柿子化简成

我考场上也化简出这个柿子了，直观的讲就是在区间中找出和 互质的数，然后就是最简单的筛！

没错，就是暴力筛，我还以为需要反演或者欧拉之类的东西，因为以前见过一个类似的题目只不过 并不是给定的，所以就因为这我就没有去想筛.....

我们看怎么筛，简单，将 进行质因数分解，暴力的用每个素因子对区间进行筛除。只要和 有相同的质因子都晒去，不过可以发现，有重复。考虑容斥。

本以为这玩意直接上莫比乌斯函数就好，发现素因子是不间断的，所以我们就暴力的枚举质因子的乘积的形式，具体的，用 DFS 暴力的判断这个素因子我选还是不选。然后遵循容斥原理奇加偶减的原则大力容斥就好。

可是我代码中却是偶加奇减，这是因为我们筛的数都是不合法，最终是以 的形式求和，其中 是给定区间长度，那么这就有个负号了，自然而然的所有的加减就取反了。

/*
先写个暴力看柿子的正确性 
看来是正确的的，考虑化简 
只有奇数做贡献，复杂度/2 
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define int long long
using namespace std;
const int B=1e7+10;
const int mod=1e9+7;
int read() {int x;scanf("%lld",&x);return x;}
int n,m,k;
int pre[B],vis[B];
int cnt;
void get(int x)
{
    for (int i=2;i*i<=x;i++)
    {
        if (x%i==0) 
        {
            pre[++cnt]=i;
            while (x%i==0) x/=i;
        }
    }
    if (x>1ll) pre[++cnt]=x;
}
int len;
int ans;
void dfs(int now)
{
    if (now==cnt)
    {
        int res=1ll,tot=0;
        for (int i=1;i<=cnt;i++) 
            if (vis[i]) res=res*pre[i],tot++;
        if (res==1 || tot==0) return;
        int num=0;
        num=m/res-(n-1)/res;
        if (tot&1) ans=(ans-num);
        else ans=(ans+num);
        return;
    }
    vis[now+1]=1;
    dfs(now+1);
    vis[now+1]=0;
    dfs(now+1);
}
signed main()
{
    n=read(),m=read(),k=read();
    int res=k; 
    k=2ll*k;
    m=m-2ll*res;
    if (n>m) 
    {
        printf("%lld",0);
        return 0;
    }
    if (n==0) n=1;
    get(k);
    len=m-n+1ll; 
    ans=len;
    dfs(0);
    printf("%lld",ans);
} 
/*
5 10 1
*/