HDU4135 Co-prime [容斥]

$Co-prime$Co−prime

$Description$Description
求区间 $L,R$L,R 之间与 $N$N 互质的数的个数 , $L,R\&lt;=10^{15},N\&lt;=10^9$L,R<=1015,N<=109

$最初想法$最初想法
将 $N$N 分解质因数, 得出 $cnt$cnt 个不同的质因数, 存到 $p\left[\right]$p[] 数组中.
利用 容斥 计算 $[1,x]$[1,x] 中与 $N$N不互质的数的数量 $num$num, 互质的数量则为 $x-num$x−num.
使用 $[1,L-1],[1,R]$[1,L−1],[1,R] 的答案再 容斥 一下就可以了 .

$Attention$Attention

• $分解质数到最后时,N可能为最后的大质数,需要计入p\left[\right]$分解质数到最后时,N可能为最后的大质数,需要计入p[]
• 在容斥找 $num$num 时需要 求解 $LCM$LCM, 不能莽乘.
• DFS容斥时需要 判断是否一个数都没有选.
  

$DFS$DFS 部分:

void DFS(int k, bool opt, int p_sum, const int &x){
        if(k == cnt+1){
                if(p_sum == 1) return ;
                if(!opt) Tmp_1 -= x/p_sum;
                else Tmp_1 += x/p_sum;
                return ;
        }
        DFS(k+1, opt^1, Lcm(p_sum, p[k]), x);
        DFS(k+1, opt, p_sum, x);
}

$正解部分$正解部分
按以上解法, 将 $DFS$DFS 换成 $二进制枚举$二进制枚举 就 $AC$AC 了, 好奇怪.

症结 ↑

二进制枚举状态部分:

        for(reg int i = 1; i < 1<<cnt; i ++){
                int p_sum = 1;
                int p_cnt = 0;
                for(reg int j = 1; j <= cnt; j ++)
                        if((1<<j-1) & i) p_cnt ++, p_sum = Lcm(p_sum, p[j]);
                if(p_cnt & 1) Tmp_1 += x/p_sum;
                else Tmp_1 -= x/p_sum;
        }
        return x-Tmp_1;

$实现部分$实现部分
没什么好说的.

#include<cstdio>
#include<cctype>
#define reg register
typedef long long ll;

const int maxn = 105;

int Test_Cnt;
int N;
int cnt;
int p[maxn];
ll Tmp_1;
ll L;
ll R;

int Gcd(int a, int b){ return !b?a:Gcd(b, a%b); }
int Lcm(int a, int b){ return a/Gcd(a, b)*b; }

ll Calc(ll x){
        if(!x) return 0;
        Tmp_1 = 0;
        for(reg int i = 1; i < 1<<cnt; i ++){
                int p_sum = 1;
                int p_cnt = 0;
                for(reg int j = 1; j <= cnt; j ++)
                        if((1<<j-1) & i) p_cnt ++, p_sum = Lcm(p_sum, p[j]);
                if(p_cnt & 1) Tmp_1 += x/p_sum;
                else Tmp_1 -= x/p_sum;
        }
        return x-Tmp_1;
}

void Work(){
        scanf("%lld%lld%d", &L, &R, &N);
        cnt = 0;
        for(reg int d = 2; d*d <= N; d ++)
                if(N % d == 0){
                        p[++ cnt] = d;
                        while(N%d == 0) N /= d;
                }
        if(N > 1) p[++ cnt] = N; //Attention
        printf("Case #%d: %lld\n", ++ Test_Cnt, Calc(R) - Calc(L-1));
}

int main(){
        int T;
        scanf("%d", &T);
        while(T --) Work();
        return 0;
}