【牛客练习44:C】小y的质数（求区间内k生互斥数对数---容斥原理+质因子分解）

题目地址:https://ac.nowcoder.com/acm/contest/634/C

题意

---

求区间[l,r]内有多少对k生互斥数对数，所谓k生互斥数即（y-k,y+k）互斥，且两个数都在区间内

注意：l，r可以从0开始！数据范围比较大，要转换思维，普通方法会超时

 

解题思路

---

（终于把大佬的代码看懂了！！(;´༎ຶД༎ຶ`) 数论是知识盲点，想不出来，想出来也不会写QAQ）

[l,r]内（x,x+2k）互斥即gcd(x,x+2k)=1也就是gcd(x,2k)=1;x对应的范围是[l,r-2*k]

举例说明：如果2k的质因子有2、3、5那么只要x含有质因子2或3或5，那么gad(x,2k)!=1

所以就要找在[l,r-2*k]内有多少数字不含有和2k相同的质因子，也就是all-被（2或3或5）整除的数字个数。

两种方法：cnt为2k质因子的个数，v[]存质因子

以2k的质因子v[0]=2,v[1]=3,v[2]=5为例：

1.for循环枚举

for(ll i=0;i<1<<cnt;i++)
{
    ll p=1,f=1;
    for(ll j=0;j<cnt;j++)
    {
        if(i>>j&1)//>>的优先级比&高，判断条件：i/(2^j)是奇数
            p*=v[j],f*=-1;
    }
    ans+=x/p*f;
}

对于三个集合的容斥公式，应该是：

但是在上述代码执行的过程中只多减了一个x/30，所以最后只需要再加回一个。因为是一步一步执行下来的，所以和原本的容斥原理的式子不太一样，手动模拟一下，就明白了！！

2.递归遍历枚举

work(0,1,l,r);//r=r-2*k
void work(ll i,ll x,ll l,ll r)
{
    if(i==m)
    {
        ans+=x*(r-l);
        return;
    }
    work(i+1,x,l,r);
    work(i+1,-x,l/p[i],r/p[i]);
}

把递归的树画出来最底层就是结果，和上表中最右侧的备注里的结果是一样的

14个质因子的乘积就已经超过2e+13了，所以时间复杂度在O(1e5)左右吧（没有考虑质因子分解的复杂度。。）

 

ac代码

---

都是参考排名前几的大佬的代码，具体是谁的写的代码忘了。。(._.)

1.for循环枚举

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define  maxn 100005
typedef long long ll;
using namespace std;
ll v[maxn],l,r,k,cnt=0;
ll solve(ll x)
{
    if(x==-1) return 0;//l=0时
    ll ans=0;
    for(ll i=0;i<1<<cnt;i++)
    {
        ll p=1,f=1;
        for(ll j=0;j<cnt;j++)
        {
            if(i>>j&1)//>>的优先级比&高
                p*=v[j],f*=-1;
        }
        ans+=x/p*f;
    }
    return ans;
}
int main()
{
    scanf("%lld %lld %lld",&l,&r,&k);
    if(l+2*k>r)
        printf("0");
    else
    {
        k*=2;
        r-=k;
        for(ll i=2;i*i<=k;i++)
        {
            if(!(k%i))
            {
                v[cnt++]=i;
                while(!(k%i))
                    k/=i;
            }
        }
        if(k!=1) v[cnt++]=k;
        printf("%lld\n",solve(r)-solve(l-1));//注意写法
    }
    return 0;
}

2.递归枚举

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll l,r,n,p[100],m,i,ans;
void work(ll i,ll x,ll l,ll r)
{
    if(i==m)
    {
        ans+=x*(r-l);
        return;
    }
    work(i+1,x,l,r);
    work(i+1,-x,l/p[i],r/p[i]);
}
int main()
{
    cin>>l>>r>>n;
    n<<=1;
    r-=n;
    l--;
    if(l<0)l=0;
    if(l>=r)
    {
        puts("0");
        return 0;
    }
    for(i=2;i*i<=n;i++)if(n%i==0)
    {
        p[m++]=i;
        while(n%i==0)n/=i;
    }
    if(n>1)p[m++]=n;
    work(0,1,l,r);
    cout<<ans<<endl;
    return 0;
}