题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
import java.util.*;
class Pos{
long var;
public Pos(long var) {
this.var = var;
}
}
public class Main {
static int a;
static int b;
static int exgcd(int a,int b,Pos x,Pos y){
if(b==0){
x.var=1;
y.var=0;
return a;
}
Pos x1=new Pos(0),y1=new Pos(0);
int d=exgcd(b,a%b,x1,y1);
x.var=y1.var;
y.var=x1.var-((long)(a/b))*y1.var;
return d;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
a=sc.nextInt();
b=sc.nextInt();
Pos x=new Pos(0);
Pos y=new Pos(0);
int gcd=exgcd(a,b,x,y);
//System.out.println(gcd);
int k=b/gcd;
x.var=(x.var%k+k)%k;
System.out.println(x.var);
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla