用C++遞歸實(shí)現(xiàn)UP所講解輾轉(zhuǎn)相除法（程序很爛，僅供參考）

#include<bits/stdc++.h>

using namespace std;

bool f1=0;//用于判斷函數(shù)是否第一次調(diào)用?

struct node //用于存儲函數(shù)生成的d,k?

{

unsigned long long d;

unsigned long long k;

bool f;

};

node fd(

unsigned long long e,

unsigned long long r)

{

//用于找到合適的私鑰d?

if(f1==1)//如果不是第一次調(diào)用?

{

//輾轉(zhuǎn)相除?

if(e>r)e%=r;

else r%=e;

if(e==1)

//假設(shè)k=0

return {1,0,0};

if(r==1)

//假設(shè)d=1

return {1,e-1,1};

}

else f1=1;

node rfd=fd(e,r);

if(rfd.f==0)

return {rfd.d,((e*rfd.d-1)/r),1};//計(jì)算上一個(gè)r?

if(rfd.f==1)

return {((1+r*rfd.k)/e),rfd.k,0};//計(jì)算上一個(gè)e

}

int main()

{

//按順序輸入e,r兩個(gè)參數(shù)?

unsigned long long e,r;

cin>>e>>r;

unsigned long long d;

d=fd(e,r).d;

//輸出生成的d以及判斷d是否合法?

cout<<"d="<<d<<endl;

cout<<"判斷:"<<((d*e)%r==1)<<endl;

system("pause > nul");

return 0;

}