简答题
偏难
#23492
同余方程 【问题描述】 求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。 【输入】 输入文件为 mod.in。 输入只有一行,包含两个正整数…
同余方程
【问题描述】
求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
【输入】
输入文件为 mod.in。
输入只有一行,包含两个正整数 a, b,用一个空格隔开。
【输出】
输出文件为 mod.out。
输出只有一行,包含一个正整数 x0,即最小正整数解。输入数据保证一定有解。
【输入输出样例】

【数据范围】
对于 40%的数据,2 ≤b≤ 1,000;
对于 60%的数据,2 ≤b≤ 50,000,000;
对于 100%的数据,2 ≤a, b≤ 2,000,000,000。
答案与解析
正确答案:<p style="text-align: left;">#include <stdio.h></p><p style="text-align: left;">long long a,b,x,y,k;</p><p style="text-align: left;">void exgcd(long long a,long long b)</p><p style="text-align: left;">{</p><p style="text-align: left;"> if(b==0)</p><p style="text-align: left;"> {</p><p style="text-align: left;"> x=1;</p><p style="text-align: left;"> y=0;</p><p style="text-align: left;"> return;</p><p style="text-align: left;"> }</p><p style="text-align: left;"> exgcd(b,a%b);</p><p style="text-align: left;"> long long int temp_x = x;</p><p style="text-align: left;"> x=y;</p><p style="text-align: left;"> y = temp_x - a/b *y;</p><p style="text-align: left;"> return;</p><p style="text-align: left;">}</p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"> scanf("%lld %lld\n",&a,&b);</p><p style="text-align: left;"> exgcd(a,b);</p><p style="text-align: left;"> x = (x%b + b)%b;</p><p style="text-align: left;"> printf("%lld\n",x);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。