一:最大公約數
/**'
輾轉相除法求最大公約數,擴充歐幾米德求方程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;
}