简单数学问题

一：最大公约数

/**'
辗转相除法求最大公约数，扩展欧几米德求方程a*x+b*y=gcd(a,b) 
**/
#include<stdio.h>
#include<iostream>
using namespace std;

//辗转相除法求最大公约数
int gcd(int a,int b){
	if(b==0){
		return a;
	}
	return gcd(b,a%b);
} 

//扩展欧几米德求方程a*x+b*y=gcd(a,b) 
int extgcd(int a,int b,int& x,int& y){
	int d=a;
	if(b!=0){
		d=extgcd(b,a%b,y,x);
		y-=(a/b)*x;
	}else{
		x=1;
		y=0;
	}
	return d;
}
int main(){
	int a,b,x,y;
	scanf("%d%d",&a,&b);
	extgcd(a,b,x,y);
	printf("%d%d",x,y);
	return 0;
}
           

二：素数问题

#include<stdio.h>
#include<iostream>
#include<vector>
#include<map>
using namespace std;
//假设输入都是正数
//判断素数
bool is_prime(int n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			return false;
		}
	}
	return n!=1; //1是例外 
} 

//约数枚举
vector<int> divisor(int n){
	vector<int> res;
	for(int i=1;i*i<=n;i++){
		if(n%i==0){
			res.push_back(i);
			if(i!=n/i){
				res.push_back(n/i);
			}
		}
	}
	return res;
} 

//整数分解
map<int ,int> prime_factor(int n){
	map<int,int> res;
	for(int i=2;i*i<=n;i++){
		while(n%i==0){
			++res[i];
			n/=i;
		}
	} 
	if(n!=1){
		res[n]=1;
	}
	return res;
}

int main(){
	int x,y,z;
	vector<int> res;
	map<int,int> mres;
	scanf("%d%d%d",&x,&y,&z);
	bool is=is_prime(x);
	if(is==true){
		printf("Yes\n");
	}else{
		printf("No\n");
	}
	res=divisor(y);
	mres=prime_factor(z);
	for(int i=0;i<res.size();i++){
		printf("%d ",res[i]);
	}
	printf("\n");
	map<int,int>::iterator it;
	for(it=mres.begin();it!=mres.end();it++){
		printf("%d %d\n",it->first,it->second);
	}
	return 0;
}
           

三：快速幂运算

/**
快速幂运算，求解x的n次方 
**/
#include<stdio.h>
typedef long long ll;
ll mod_pow(ll x ,ll n,ll mod){
	ll res=1;
	while(n){
		//如果n的二进制最后一位为1，即n为奇数 
		if(n&1){
			res=res*x%mod; 
		} 
		x=x*x%mod;
		//n减少一半 
		n>>=1;
	}
	return res;
}
int main(){
	printf("%d",mod_pow(156,562,50));
	return 0;
}