hihoCoder1461 Rikka with Number

题面在这里

这个过程的逆过程是辗转相减

那么只需要随机一个\(m\in [1,n]\),使得n,m互质切步数不超过60即可

操作次数可以求gcd时算

示例程序:

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
#include<cstdio>
#include<algorithm>
using namespace std;

int tst,a,b,tot,stk[10000];
#define brand() ((long long)rand()*rand())
inline int gcd(int x,int y) {return y==0?x:(tot+=x/y,gcd(y,x%y));}
int main(){
scanf("%d",&tst);
while (tst--){
scanf("%d",&a);
int MIN=999,t;
for (int i=1;i<=1000&&MIN>60;i++){
tot=0;
if (gcd(a,t=brand()%(a-1)+1)==1)
if (MIN>tot) MIN=tot,b=t;
}
stk[0]=0;
while (a+b!=1)
if (a>b) a-=b,stk[++stk[0]]=0;
else b-=a,stk[++stk[0]]=1;
if (a==0&&b==1) while (stk[0]) printf("%d",stk[stk[0]--]);
else while (stk[0]) printf("%d",1-stk[stk[0]--]);
printf("\n");
}
return 0;
}