简答题 偏难
#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 &lt;stdio.h&gt;</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",&amp;a,&amp;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>
这道题暂未补解析。