給出2個(gè)數(shù)M和N(M < N)，且M與N互質(zhì)，找出一個(gè)數(shù)K滿足0 < K < N且K * M % N = 1，如果有多個(gè)滿足條件的，輸出最小的。 Input 輸入2個(gè)數(shù)M, N中間用空格分隔（1 <= M < N <= 10^9) Output 輸出一個(gè)數(shù)K，滿足0 < K < N且K * M % N = 1，如果有多個(gè)滿足條件的，輸出最小的。 Input示例 2 3 Output示例 2
#include<stdio.h>typedef __int64 LL;LL exGcd(LL a,LL b,LL &x,LL &y){ if(!b){ x=1,y=0; return a; } LL d=exGcd(b,a%b,x,y); LL t=x; x=y; y=t-a/b*y; return d;}int main(){ LL M,N,x,y; scanf("%lld%lld",&M,&N); exGcd(M,N,x,y); LL ans=(N+x%N)%N;新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
