几个数论小算法

快速幂

个人感觉用的不多

int quick_pow(int a,int b){
    if(a==0)return 0;//这是个坑
    int ans=1;
    while(b)
	{
        if(b&1)
		ans*=a;  //取最后一位 
        b>>=1;   //右移 
		a*=a;    //a , a^2 ,a^4 ,a^8 
    }
    return ans;
}

快速幂取模

有时候幂运算所得到结果过大，导致溢出。而我们只想得到最后取模的结果。
原理 (ab) % c = ( (a%c)(b%c) ) % c

long long quick (long long a,long long b,long long MOD)
{
    if(a==0)return 0;//这是个坑
	long long ans = 1;
	while (b > 0)
	{
		if (b & 1)   //取最后一位，判断是1还是0 
		ans = (ans * a )%MOD; 
		b = b >> 1;  //移位 ，去掉最后一位 
		a = (a * a)%MOD;
	}
	return ans % MOD;  //返回结果
}

求最大公约数

int gcd (int a,int b)
{
	if (b == 0)
	return a;
	else
	return gcd(b,a%b);
}

求解ax + by = gcd(a , b) = d

这里解出来的是特解

#define LL long long

void ex_gcd(LL a,LL b,LL& x,LL& y,LL& d)
{
	LL temp;
	if (b == 0)
	{
		x = 1;	y = 0;	d = a;
	}
	else
	{
	ex_gcd(b, a%b, x, y, d); 
 	temp = x;			//关键语句 
	x = y;				
	y = temp-(a/b)*y;   	
	}		
}

求解 ax + by = c

c必须要是 gcd(a,b) 的整数倍才有解
如果要求得到的x是正数，则加上 x1 = (x1%b+b)%b;

#include <stdio.h>
#define LL long long

void ex_gcd(LL a,LL b,LL& x,LL& y,LL& d)
{
	LL temp;
	if (b == 0)
	{
		x = 1;	y = 0;	d = a;
	}
	else
	{
	ex_gcd(b, a%b, x, y, d); 
 	temp = x;			//关键语句 
	x = y;				
	y = temp-(a/b)*y;   	
	}	
	
}

int fun(LL a,LL b,LL& x1,LL& y1,LL& c) 
{
	LL x,y,d;
	ex_gcd(a,b,x,y,d);
	if(c%d == 0)    //判断是否有解
	{
		x1 = x * c/d;
        //x1 = (x1%b+b)%b; //当x1不是正数是，变为正数
		y1 = y * c/d;
		return 1;
	}
	else 
	return 0;
	
}

int main(int argc, char *argv[])
{
	LL a,b,c;
	LL x1,y1;
	scanf("%lld%lld%lld",&a,&b,&c);
	if ( fun(a,b,x1,y1,c) )
	{
		printf("%lld %lld",x1,y1);
	}
	else 
	printf("error,impsooible");
	return 0;
}