HDU 4135 Co-prime 容斥原理

Description

给出区间[L, R]，给出数字N，求在该区间里与N互质的数字的个数

Analyze

在区间[L, R]里与N互质的数字的个数

== 在区间[1, R]里与N互质的数字的个数

减去( - ) 在区间[1, L]里与N互质的数字的个数

所以可以自定义一个函数求出[1, up]里与N互质的数的个数

但是数字太多，依次找互质的数字不好找，但找不互质的容易

区间[1, up]里N的质因子的倍数与N不互质

找到一个质因子可找到一大堆它的倍数(与N不互质的数字)

像找2、3、5…的倍数时有重复(6,10,15)，这便用到容斥!

Code

#include <map>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long

ll factor[100005], cnt = 0;

void get_factors(ll n)///①得到全集②进行容斥
{
    cnt = 0;
    for(ll i = 2; i * i <= n; ++i)
    {
        if(n % i == 0)
        {
            factor[cnt++] = i;
            while(n % i == 0)
                n /= i;
        }
    }
    if(n != 1)
        factor[cnt++] = n;
}

ll Rongchi_queue(ll up)///计算 1 ~ up 内有几个 与n不互质(n)
{
    ll t = 0, q[100005], res = 0;
    q[t++] = -1;
    for(ll i = 0; i < cnt; ++i)
    {
        ll up = t;
        for(ll j = 0; j < up; ++j)
            q[t++] = q[j] * factor[i] * -1;
    }
    for(ll i = 1; i < t; ++i)
        res += up / q[i];
    return res;
}

ll Rongchi_binary(ll up)
{
    ll res = 0;
    for(ll i = 1; i < (1 << cnt); ++i)
    {
        ll tem = 1, tot = 0;
        for(ll j = 0; j < cnt; ++j)
            if(i & (1 << j))
            {
                tot++;
                tem *= factor[j];
            }
        if(tot & 1)
            res += up / tem;
        else
            res -= up / tem;
    }
    return res;
}

ll sum = 0;
void DFS(ll num, ll used, ll up, ll mu, ll sth)
{
    if(used == up)
    {
        sum += sth / mu;
        return;
    }
    if(num == cnt)
        return ;
    DFS(num + 1, used, up, mu, sth);
    DFS(num + 1, used + 1, up, mu * factor[num], sth);
}

ll Rongchi_DFS(ll up)
{
    ll res = 0;
    for(ll i = 1; i <= cnt; ++i)
    {
        sum = 0;
        DFS(0, 0, i, 1, up);
        if(i & 1)
            res += sum;
        else
            res -= sum;
    }
    return res;
}

int main()
{
    int t, tot = 1;
    ll left, right, n;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%lld%lld%lld", &left, &right, &n);
        get_factors(n);
//        ll ans = Rongchi_queue(right) - Rongchi_queue(left - 1);
//        ll ans = Rongchi_binary(right) - Rongchi_binary(left - 1);
        ll ans = Rongchi_DFS(right) - Rongchi_DFS(left - 1);
        ans = right - (left - 1) - ans;
        cout << "Case #" << tot++ << ": ";
        cout << ans << '\n';
    }
    return 0;
}