基础数论模版

谁践踏了优雅 2022-08-09 14:40 182阅读 0赞

欧拉函数值，小于n且与n互质的数的个数

#include <iostream>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    using namespace std;
    
    const int maxn = 1000005;
    int p[maxn];//m[i]保存i的欧拉函数
    
    int Eular(int n)
    {
        //求解单独一个数字的欧拉函数值
        int ans=n;
        for(int i = 2 ; i*i <= n ; i++)
        {
            if(n%i == 0)
            {
                n/=i;
                ans-=ans/i;
                while(n%i==0)
                {
                    n/=i;
                }
            }
        }
        if(n>1)
        {
            ans-=ans/n;
        }
        return ans;
    }

//求出1到n范围内的所有数的欧拉函数
    void solve_Euler()
    {
        memset(p,0,sizeof(p));
        for(int i = 2 ; i <= 1000000 ; i++)
        {
            //利用筛选发求p[i]
           if(!p[i])
           {
               for(int j = i ; j <= 1000000 ; j+=i)
               {
                   if(!p[j])
                   {
                       p[j]=j;
                   }
                   p[j]=p[j]/i*(i-1);
               }
           }
        }
    }
    
    int main()
    {
        int n;
        solve_Euler();
        //cout<<p[1]<<endl;
        while(scanf("%d",&n)!=EOF && n)
        {
            long long num=0;
            for(int i = 2 ; i <= n ; i++)
            {
                num+=p[i];
            }
            printf("%I64d\n",num);
        }
        return 0;
    }

素数筛选法求1到n之间的素数

#include <iostream>
    #include <string>using namespace std;
    
    const int MAX=20000;
    bool prime[MAX];
    //prime[i]=1代表i是素数
    
    void Filterprime()
    {
        memset(prime,true,sizeof(prime));
        prime[0]=false;
        prime[1]=false;
        int i;
        for (i = 2;i*i <= MAX;i++)
        {
            if (prime[i])
            {
                int j = i*2;
                while (j <= MAX)
                {
                    prime[j]=false;
                    j+=i;
                }
            }
        }
    }
    
    int main()
    {
        Filterprime();
        int n,count=1;
        while (cin>>n&&n>0)
        {
            if (prime[n] &&n!=2)
            {
                cout<<count++<<": yes"<<endl;
            }
            else cout<<count++<<": no"<<endl;
     }

扩展欧几里德算法是用来在已知a, b求解一组x，y使得a\*x+b\*y=Gcd(a,b)(解一定存在，根据数论中的相关定理)

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    int ExGcd(int a,int b,int &x,int &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        int r=ExGcd(b,a%b,x,y);
        int t=x;
        x = y;
        y = t-a/b*y;
        return r;
    }
    
    int main()
    {
        int a,b,x,y;
        while(scanf("%d%d",&a,&b)!=EOF)
        {
            ExGcd(a,b,x,y);
            printf("%d %d\n",x,y);
        }
        return 0;
    }

不定方程方程求解的问题 , 求a \* x + b \* y = n的整数解

1、先计算Gcd(a,b)，若n不能被Gcd(a,b)整除，则方程无整数解；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a' \* x + b' \* y = n'，此时Gcd(a',b')=1;

2、利用上面所说的欧几里德算法求出方程a' \* x + b' \* y = 1的一组整数解x0,y0，则n' \* x0,n' \* y0是方程a' \* x + b' \* y = n'的一组整数解(也是原方程的一组整数解)；

3、根据数论中的相关定理，可得方程a' \* x + b' \* y = n'的所有整数解为：

x = n' \* x0 + b' \* t

y = n' \* y0 - a' \* t(t为整数)

上面的解也就是a \* x + b \* y = n 的全部整数解。

#include <iostream>
    using namespace std;
    
    __int64 t,p;
    
    __int64 euclid(__int64 a,__int64 b){
    	if(b==0)
    		return a;
    	else
    		return euclid(b,a%b);
    }
    
    void extended_euclid(__int64 a,__int64 b){
    	if(b==0){
    		t=1;
    		p=0;
    	}
    	else{
    		__int64 temp;
    		extended_euclid(b,a%b);
    		temp=t-a/b*p;
    		t=p;
    		p=temp;
    	}
    }
    
    int main(){
    	__int64 x,y,n,m,L,gcd;
    	cin>>x>>y>>m>>n>>L;
    	if (m==n){
    		cout<<"Impossible"<<endl;
    		return 0;
    	}
    	__int64 a,b,c,c1;
    	a=n-m;
    	b=L;
    	c=x-y;   //由题意构建的a,b,c...a*x+b*y=c;
    	gcd=euclid(a,b);
    	c1=c%gcd;
    	if (c1!=0){
    		cout<<"Impossible"<<endl;
    		return 0;
    	}
    	c/=gcd;
    	a/=gcd;
    	b/=gcd;   
    	extended_euclid(a,b);
    	t*=c;
    	p*=c;
    	t=(t%b+b)%b;
    	cout<<t<<endl;
    	return 0;
    }

模线性方程ax=b (mod n)  求X的值。

该方程有解的充要条件为 gcd(a,n) | b ，即 b% gcd(a,n)==0.

当有解时，关键在于计算最大公约数 d=gcd(a,n) 与 最小解x0

引入欧几里得扩展方程  d=ax+by

注意：

计算n=2^k时，用位运算是最快的，1<<k （1左移k位）就是2^k

但是使用long long要注意格式， 1LL<<k

使用\_\_int64要强制类型转换 (\_\_int64)1<<k

#include <iostream>
    #include <cstdio>
    using namespace std;
    
    //d=ax+by,其中最大公约数d=gcd(a,n)，x、y为方程系数，返回值为d、x、y
    __int64 EXTENDED_EUCLID(__int64 a,__int64 b,__int64& x,__int64& y)
    {
    	if(b==0)
    	{
    		x=1;
    		y=0;
    		return a;  //d=a，x=1,y=0,此时等式d=ax+by成立
    	}
    	__int64 d=EXTENDED_EUCLID(b,a%b,x,y);
    	__int64 xt=x;
    	x=y;
    	y=xt-a/b*y;  //系数x、y的取值是为满足等式d=ax+by
    	return d;
    }
    
    int main(void)
    {
    	__int64 A,B,C,k;
    	while(scanf("%I64d %I64d %I64d %I64d",&A,&B,&C,&k))
    	{
    		if(!A && !B && !C && !k)
    			break;
    
    		__int64 a=C;
    		__int64 b=B-A;
    		__int64 n=(__int64)1<<k;  //2^k
    		__int64 x,y;
    		__int64 d=EXTENDED_EUCLID(a,n,x,y);  //求a,n的最大公约数d=gcd(a,n)和方程d=ax+by的系数x、y
    
    		if(b%d!=0)  //方程 ax=b(mod n) 无解
    			cout<<"FOREVER"<<endl;
    		else
    		{
    			x=(x*(b/d))%n;  //方程ax=b(mod n)的最小解
    			x=(x%(n/d)+n/d)%(n/d);  //方程ax=b(mod n)的最整数小解
    			printf("%I64d\n",x);
    		}
    	}
    	return 0;
    }