HDU 4135 Co-prime（容斥原理）

題目連結

題意

給你三個整數a,b,c求[a,b]區間内與n互質數個數

思路

即求[a,b]區間内與n不互質數個數，即将n進行素數拆分

一個數是某個拆分數的倍數即不互質，如wtf/素數pri 為 1到wtf間與pri不互質的個數）

素數拆分有很多，會重複計數，用容斥原理剔除。

ans = r-(l-1) - ( solve( r ) - solve( l-1 ) )

代碼（含兩種版本）

遞歸版

#include <stdio.h>

#define ll long long

ll l, r, num[100], len;

ll dfs(ll n, ll x)
{
    ll tmp = 0;
    for(ll i = x; i < len; ++i) tmp += n/num[i] - dfs(n/num[i], i+1);
    return tmp;
}

int main()
{
    ll t, ca = 1, n;
    for(scanf("%lld",&t); ca <= t; ++ca)
    {
        scanf("%lld%lld%lld",&l,&r,&n);
        len = 0;
        for(ll i = 2; i*i <= n; ++i)
        {
            if(n%i == 0)
            {
                num[len++] = i;
                while(n%i == 0) n /= i;
            }
        }
        if(n > 1) num[len++] = n;
        printf("Case #%lld: %lld\n",ca, r-(l-1) - (dfs(r, 0) - dfs(l-1, 0)));
    }
    return 0;
}

           

二進制版本

#include <stdio.h>

#define ll long long

ll l, r, num[100], len;

ll solve(ll n)
{
    ll ans = 0;
    for(ll i = 1; i < (1ll<<len); ++i)
    {
        ll tmp = 0, wtf = 1;
        for(ll j = 0; j < len; ++j)
        {
            if((1ll<<j) & i)
            {
                wtf *= num[j];
                tmp ^= 1;
            }
        }
        ans += tmp ? n/wtf : -n/wtf;
    }
    return ans;
}

int main()
{
    ll t, ca = 1, n;
    for(scanf("%lld",&t); ca <= t; ++ca)
    {
        scanf("%lld%lld%lld",&l,&r,&n);
        len = 0;
        for(ll i = 2; i*i <= n; ++i)
        {
            if(n%i == 0)
            {
                num[len++] = i;
                while(n%i == 0) n /= i;
            }
        }
        if(n > 1) num[len++] = n;
        printf("Case #%lld: %lld\n",ca, r-(l-1) - (solve(r) - solve(l-1)));
    }
    return 0;
}