HDU 5768 Lucky7（数论）

电玩女神 2022-07-16 23:26 181阅读 0赞

题目链接：  
http://acm.split.hdu.edu.cn/showproblem.php?pid=5768

题目大意：求出一个区间内模7余0，但是模一些给定的互素的数不等于其给定的值的数的个数。如求1-100中模7余0，但是不能模3余2，模5余3的数的个数。

解题思路：首先可以知道通过中国剩余定理能求出一个区间内模3余2，模5余3，等式的所有解，这道题就是在模7余0的基础上求那些式子的并集，用容斥定理就好了。

中国剩余定理：

![这里写图片描述][a5aa55e1d335f7ee4d1c7efde31c39f4.png]

容斥定理：《挑战程序设计竞赛》295页

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <vector>
    #include <algorithm>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9+7;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    int a[100];
    int m[100];
    int cond1[100];
    int cond2[100];
    
    LL extent_Euclid(LL a,LL b,LL &x,LL &y);
    
    LL x2,y2;
    LL quik_cheng(LL a,LL b,LL m)
    {
        LL res=0;
        while(a)
        {
            if(a&1) res=(res+b)%m;
             b=(b*2)%m;
            a>>=1;
        }
        return res;
    }
    LL CRT(int a[],int m[],int n)
    {
        LL M=1;
        LL ans=0;
        for(int i=0;i<n;i++)
        {
            M*=m[i];
        }
        for(int i=0;i<n;i++)
        {
            LL x,y;
            LL Mi=M/m[i];
            extent_Euclid(Mi,m[i],x,y);
            x=(x%M+M)%M;
            LL ex=quik_cheng(Mi%M,x,M);
            ans=ans+quik_cheng(ex,a[i],M);
        }
        while(ans<0) ans+=M;
         ans=ans-ans/M*M;
        if(ans>y2) return 0;
        if(ans>=x2&&ans<=y2)
        {
            LL tt=(y2-ans)/M+1;
            return tt;
        }
        if(ans<x2)
        {
            LL x3=x2-ans-1;
            LL y3=y2-ans;
            LL tt=y3/M-x3/M;
            return tt;
        }
    
    }
    
    int main()
    {
        int T,n,casee=1;
        RI(T);
        while(T--)
        {
            RI(n);
            scanf("%I64d%I64d",&x2,&y2);
            a[0]=0;//a为取余等于几
            m[0]=7;//m为取余的数
            for(int i=0;i<n;i++)
            {
                RII(cond1[i],cond2[i]);
            }
            LL ans=0;
            /*for(int i=0;i<n;i++)
            {
                cout<<cond1[i]<<"   "<<cond2[i]<<endl;
            }*/
            for(int i=1;i<(1<<n);i++)
            {
                int num=0;
                int poi=1;
                for(int j=i;j!=0;j>>=1) num+=j&1;
    
                for(int j=0;j<n;j++)
                {
                    if((i>>j)&1)
                    {
                        a[poi]=cond2[j];
                        m[poi]=cond1[j];
                        poi++;
                    }
                }
                if(num%2==1)  ans+=CRT(a,m,poi);
                else ans-=CRT(a,m,poi);
    
            }
            printf("Case #%d: %I64d\n",casee,y2/7-(x2-1)/7-ans);
            casee++;
        }
        return 0;
    }
    
    
    
    LL extent_Euclid(LL a,LL b,LL &x,LL &y)
    {
        LL d=a;
        if(b!=0){
            d=extent_Euclid(b,a%b,y,x);
            y-=(a/b)*x;
        }
        else{
            x=1;
            y=0;
        }
        return d;
    }

[a5aa55e1d335f7ee4d1c7efde31c39f4.png]: /images/20220717/39584b61be6744ae9ad316f67c1a6a67.png