44 条题解

• @ 2017-11-08 17:18:15
``````#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
ll a,b;

ll exgcd(ll a,ll b,ll &x,ll &y)
{
if(b==0)
{
x=1;y=0;
return a;
}
ll ret=exgcd(b,a%b,x,y);
ll buf=x;x=y;y=buf-a/b*y;
return ret;
}

int main()
{
scanf("%lld%lld",&a,&b);
ll x,y;
ll gcd=exgcd(a,b,x,y);
x=(x%b+b)%b;
printf("%lld",x);
}
``````
• @ 2017-10-27 16:46:43

很裸的扩欧

``````#include <iostream>
#include <iomanip>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <vector>
#include <queue>
using namespace std;
int a,b,x,y,k;
void gcd(int m,int n)
{
if(n==0)
{
x=1;
y=0;
return;
}
gcd(n,m%n);
k=x;
x=y;
y=k-m/n*y;
return;
}
int main()
{
scanf("%d%d",&a,&b);
gcd(a,b);
printf("%d",(x+b)%b);
return 0;
}
``````
• @ 2020-01-29 02:33:55

pow(a, -1, b) # Python 3.8

• @ 2017-10-27 20:43:01

扩欧

``````#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL;
void gcd(LL a, LL b, LL &d, LL &x, LL &y) {
if (!b) {d = a, x = 1, y = 0;}
else {gcd(b, a % b, d, y, x); y -= x * (a / b); }
}
int main() {
LL a, b, GCD, x, k;
scanf("%lld %lld", &a, &b);
gcd(a, b, GCD, x, k);
LL ta = b / GCD;
while (x < 0) x += ta;
printf("%lld", x);
return 0;
}
``````
• @ 2017-10-18 16:49:13
``````#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <deque>
using namespace std;

long long ext_gcd_1(long long a,long long b,long long &x,long long &y)
{
if (b==0)
{
x=1,y=0;
return a;
}
else
{
long long ans=ext_gcd_1(b,a%b,x,y);
long long temp=x;
x=y;
y=temp-(a/b)*y;
return ans;
}
}

long long a,b,x,y;

int main()
{
scanf("%lld%lld",&a,&b);
long long temp=ext_gcd_1(a,b,x,y);
printf("%lld\n",(x+b)%b);
}
``````
• @ 2017-10-18 16:50:05

很H2O的题

• @ 2017-10-12 22:23:00
``````#include <iostream>
#include <algorithm>
using namespace std;
#define For(aHJEfaks, fwbjkWK, AENGIBv) for (int aHJEfaks = fwbjkWK; aHJEfaks <= AENGIBv; ++aHJEfaks)
#define For2(aHJEfaks, fwbjkWK, AENGIBv) for (auto aHJEfaks = fwbjkWK; aHJEfaks != AENGIBv; ++aHJEfaks)
long long a0, b0;
typedef pair<long long, long long> pa;
pa s(long long a, long long b){
if (a == 1){
return make_pair(1, 0);
}
if (b == 1){
return make_pair(0, 1);
}
if (a > b){
long long q = a / b;
long long r = a % b;
pa tms = s(r, b);
return make_pair(tms.first, tms.second - q * tms.first);
}
if (a < b){
long long q = b / a;
long long r = b % a;
pa tnm = s(a, r);
return make_pair(tnm.first - q * tnm.second, tnm.second);
}
}
int main(){
cin >> a0 >> b0;
long long tem = s(a0, b0).first;
long long ans = 0;
if (tem > 0) {
ans = tem - (tem / b0) * b0;
}
if (tem < 0){
ans = tem - (tem / b0 - 1) * b0;
}
cout << ans << endl;
return 0;
}

``````
• @ 2017-09-06 18:22:56
``````#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;
void exgcd(int a, int b, int &x, int &y)
{
if(a==1){
x=1;y=0;
return;
}
exgcd(b,a%b,x,y);
int temp=x;
x=y;
y=temp-a/b*y;
}
int main()
{
int a,b,x,y;
cin>>a>>b;
exgcd(a,b,x,y);
if(x<1)x+=b;
cout<<x<<endl;
system("pause");
return 0;
}
//此题所用拓展欧几里得算法
//详见http://blog.csdn.net/zhjchengfeng5/article/details/7786595
``````
• @ 2017-08-15 21:49:07

裸地模板题，，

``````#include <algorithm>
#include  <iostream>
#include   <cstring>
#include    <cstdio>
#include     <cmath>
using namespace std;

void exgcd(int a, int b, int& x, int& y) {
if(!b) { x = 1; y = 0; return; }
int q = a/b, r = a%b;
exgcd(b, r, y, x);
y -= q*x;
}

int inv (int a, int b) {
int x, y;
exgcd(a, b, x, y);
return x;
}

int main() {

int n, Mod;
scanf("%d%d", &n, &Mod);
int sum = inv(n, Mod);
if(sum < 0) sum += Mod;
printf("%d", sum);

return 0;
}
``````
• @ 2017-05-20 10:39:20

#include <iostream>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(i=1;i<=n;i++)
using namespace std;
void exgcd(int a, int b, int &x, int &y){
if(b==0){
x = 1; y = 0;
return;
}
exgcd(b,a%b,y,x);
y -= a/b*x;
}
int main(){
int i, j, n, m, a, b;
scanf("%d%d", &a, &b);
exgcd(a,b,n,m);
printf("%d",(n+b)%b);
return 0;
}
exgcd求逆元裸题= =

• @ 2016-11-18 18:25:24
``````program
emod;

uses
math;

var
a, b, x, y: longint;

procedure egcd(a, b: longint; var x, y: longint);
var
temp: longint;
begin
if b = 0 then
begin
x := 1;
y := 0;
exit;
end;
egcd(b, a mod b, x, y);
temp := x;
x := y;
y := temp - (a div b) * y;
end;

begin
//    assign(input, 'mod.in'); assign(output, 'mod.out');
//    reset(input); rewrite(output);
egcd(a, b, x, y);
while x < 0 do
inc(x, b);
write(x);
//    close(input); close(output);
end.
``````
• @ 2016-11-09 18:54:58
• @ 2016-10-02 13:54:42

强行不用exgcd（虽然复杂度加了个sqrt()）
由欧拉定理得,如果a和n互质，那么

a^phi(n) 同余 1(mod n)
所以
a^(phi(n)-1) 就是a在mod n意义下的乘法逆元
算phi是O(sqrt(n))的
快速幂是O(logn)的
总复杂度O(sqrt(n))

``````#include<bits/stdc++.h>
using namespace std;
inline int phi(int x)
{
int tail = sqrt(x) + 1e-6;
int ans = x;
for (int i = 2;i <= tail;i++)
{
if (!(x % i))
{
ans = ans / i *(i - 1);
while (!(x%i))x /= i;
}
}
if (x != 1)ans = ans / x *(x - 1);
return ans;
}
int mod;
int qpow(int x, int y)
{
if (y == 0)return 1;
if (y == 1)return x;
if (y == 2)return (long long)x*x%mod;
if (y == 3)return (long long)x*x%mod*x%mod;
int tmp = qpow(x, y >> 1);
tmp = (long long)tmp * tmp % mod;
if (y & 1)tmp = (long long )tmp * x % mod;
return tmp;
}
int main()
{
int a, b;
scanf("%d%d", &a, &b);
mod = b;
printf("%d\n", qpow(a, phi(b) - 1));
}
``````
• @ 2016-09-25 22:09:36
``````#include <iostream>
using namespace std;

void gcd(int a, int b, int& x, int& y){
if(b != 0){
gcd(b, a%b, x, y);
int r = x;
x = y;
y = r - (a / b) * x;
}
else
x = 1, y = 0;
}

int main(){
int a, b, x, y;
cin>>a>>b;
gcd(a, b, x, y);
cout<<(x + b) % b<<endl;
return 0;
}
``````
• @ 2016-09-25 21:56:29
``````#include <iostream>
using namespace std;

void ex_gcd(int a, int b, int& x, int& y){
if(b != 0){
ex_gcd(b, a%b, x, y);
int bri = x;
x = y;
y = bri - (a / b) * x;
}
else
x = 1, y = 0;
}

int main(){
int a, b, x, y;
cin>>a>>b;
ex_gcd(a, b, x, y);
cout<<(x + b) % b<<endl;
return 0;
}
``````
• @ 2016-09-19 00:23:48

#include <iostream>
using namespace std;

void ex_gcd(int a, int b, int& x, int& y){
if(b != 0){
ex_gcd(b, a%b, x, y);
int bri = x;
x = y;
y = bri - (a / b) * x;
}
else
x = 1, y = 0;
}

int main(){
int a, b, x, y;
cin>>a>>b;
ex_gcd(a, b, x, y);
cout<<(x + b) % b<<endl;
return 0;
}

• @ 2016-09-18 18:36:45
``````#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long LL;

void gcd (LL a, LL b, LL &d, LL &x, LL &y) {
if (!b) { d = a; x = 1; y = 0;}
else { gcd(b, a%b, d, y, x); y -= x*(a/b);}
}

int main ()
{
freopen("in.txt", "r", stdin);
LL a, b;
cin >> a >> b;
LL d, x, y;
gcd(a, b, d, x, y);
if(x < 0) while (x < 0) x += b;
else while (x > b) x -= b;
cout << x;
return 0;
}
``````
• @ 2016-09-17 10:40:02

var
a,b,x:longint;
begin
x:=1;
while (a*x) mod b<>1 do begin
x:=x+1;
end;
writeln(x);
end.

• @ 2016-11-01 19:52:45

绝壁超时

• @ 2016-09-17 10:39:45

var
a,b,x:longint;
begin
x:=1;
while (a*x) mod b<>1 do begin
x:=x+1;
end;
writeln(x);
end.

• @ 2016-11-01 19:53:02

绝壁超时

• @ 2016-07-13 08:27:58

同余方程都不知道 ，咋做
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int x,y;
void gcd(int a,int b)
{
if (a%b==0)
x=0,y=1;
else
{
gcd(b,a%b);
int t=x;
x=y,y=t-(a/b)*y;
}
}
int main()
{
int a,b;
cin>>a>>b;
gcd(a,b);
cout<<(x%b+b)%b;
}

• @ 2016-07-12 20:59:31

就是求乘法逆元，拓展欧几里得算法。
~~~
#include <cstdio>
int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;
y=0;
return a;
}
int ans=exgcd(b,a%b,x,y);
int temp=x;
x=y;
y=temp-(a/b)*y;
return ans;
}
int main(){
int a,b,x,y;
scanf("%d%d",&a,&b);
exgcd(a,b,x,y);
while(x<=0)x+=b;
printf("%d\n",x);
}

ID
1781

4

3860

1507

39%

9