NOIP2012同余方程
题目描述
求关于 x 的同余方程 ax ≡ 1 (mod b)的最小正整数解。
输入
输入文件为 mod.in。
输入只有一行，包含两个正整数 a, b，用一个空格隔开。
输出
输出文件为 mod.out。
输出只有一行，包含一个正整数 x0，即最小正整数解。输入数据保证一定有解。
样例输入
3 10
样例输出
7
提示
「数据范围」
对于 40%的数据，2 ≤b≤ 1,000；
对于 60%的数据，2 ≤b≤ 50,000,000；
对于 100%的数据，2 ≤a, b≤ 2,000,000,000。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #define mod 1000000007 #define ll long long #define inf (1LL<<60) using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans; int a,b; void exgcd(int a,int b,int &x,int &y) { if(b==0){x=1;y=0;return;} exgcd(b,a%b,x,y); int t=x;x=y,y=t-a/b*y; } int main() { a=read();b=read(); int x,y; exgcd(a,b,x,y); x=(x%b+b)%b; cout<<x<<endl; return 0; } |
计数器 9793314
OI 课件=>
OI 课件=>
黄学长高考加油！
谢 已懂
问一下
Apache is functioning normally
是什么意思
我的blog 显示的