QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#512922#9167. Coprime Arrayucup-team3591#AC ✓6ms1592kbC++141.6kb2024-08-10 16:18:262024-10-14 07:52:04

Judging History

你现在查看的是最新测评结果

  • [2024-10-14 07:52:04]
  • 管理员手动重测本题所有获得100分的提交记录
  • 测评结果:AC
  • 用时:6ms
  • 内存:1592kb
  • [2024-08-11 17:38:28]
  • hack成功,自动添加数据
  • (/hack/775)
  • [2024-08-10 16:18:27]
  • 评测
  • 测评结果:100
  • 用时:5ms
  • 内存:1536kb
  • [2024-08-10 16:18:26]
  • 提交

answer

#include<cstdio>
typedef long long ll;
inline ll read(){
	ll x=0;
	int f=0,ch=0;
	while(ch<48||ch>57) f=(ch=='-'),ch=getchar();
	while(ch>47&&ch<58) x=(x<<3)+(x<<1)+(ch&15),ch=getchar();
	return f?-x:x;
}
inline void write(ll x,char end=' '){
	if(x==0){
		putchar('0');
		putchar(end);
		return;
	}
	if(x<0) putchar('-'),x=-x;
	int ch[40]={0},cnt=0;
	while(x){
		ch[cnt++]=(int)(x%10);
		x/=10;
	}
	while(cnt--) putchar(ch[cnt]+48);
	putchar(end);
}
inline int min(int x,int y){return x<y?x:y;}
const int inf=1e9;
inline int gcd(int x,int y){
	if(x<0) x=-x;
	if(y<0) y=-y;
	return y==0?x:gcd(y,x%y);
}
int mn[1005],to[1005];
int main(){
	int s=read(),x=read();
	if(gcd(s,x)==1){
		printf("1\n%d\n",s);
		return 0;
	}
	if(gcd(s-1,x)==1){
		printf("2\n1 %d\n",s-1);
		return 0;
	}
	if(s+1<=inf&&gcd(s+1,x)==1){
		printf("2\n-1 %d\n",s+1);
		return 0;
	}
	mn[0]=0;
	to[0]=0;
	for(int i=1;i<=1000;++i){
		mn[i]=i;
		to[i]=i-1;
		for(int j=1;j<=i;++j){
			if(gcd(j,x)==1){
				if(mn[i-j]+1<mn[i]){
					mn[i]=mn[i-j]+1;
					to[i]=i-j;
				}
			}
		}
	}
	int mnpos=0,nowmn=s;
	for(int i=2;i<=1000;++i){
		if(gcd(s-i,x)==1){
			int need=mn[i]+1;
			if(need<nowmn){
				nowmn=need;
				mnpos=i;
			}
		}
		if(s+i<=inf&&gcd(s+i,x)==1){
			int need=mn[i]+1;
			if(need<nowmn){
				nowmn=need;
				mnpos=i;
			}
		}
	}
	printf("%d\n",nowmn);
	if(gcd(s-mnpos,x)==1){
		printf("%d ",s-mnpos);
		while(mnpos) write(mnpos-to[mnpos]),mnpos=to[mnpos];
	}
	else{
		printf("%d ",s+mnpos);
		while(mnpos) write(to[mnpos]-mnpos),mnpos=to[mnpos];
	}
	return 0;
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 1532kb

input:

9 6

output:

3
7 1 1 

result:

ok Correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 1592kb

input:

14 34

output:

2
1 13

result:

ok Correct

Test #3:

score: 0
Accepted
time: 2ms
memory: 1476kb

input:

1000000000 223092870

output:

2
999999971 29 

result:

ok Correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 1492kb

input:

2 1000000000

output:

2
1 1

result:

ok Correct

Test #5:

score: 0
Accepted
time: 5ms
memory: 1472kb

input:

649557664 933437700

output:

2
649557671 -7 

result:

ok Correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 1520kb

input:

33396678 777360870

output:

2
1 33396677

result:

ok Correct

Test #7:

score: 0
Accepted
time: 5ms
memory: 1500kb

input:

48205845 903124530

output:

3
48205847 -1 -1 

result:

ok Correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 1516kb

input:

251037078 505905400

output:

2
1 251037077

result:

ok Correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 1500kb

input:

30022920 172746860

output:

2
1 30022919

result:

ok Correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 1524kb

input:

63639298 808058790

output:

2
-1 63639299

result:

ok Correct

Test #11:

score: 0
Accepted
time: 5ms
memory: 1520kb

input:

76579017 362768406

output:

3
76579015 1 1 

result:

ok Correct

Test #12:

score: 0
Accepted
time: 6ms
memory: 1516kb

input:

40423669 121437778

output:

3
40423667 1 1 

result:

ok Correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 1508kb

input:

449277309 720915195

output:

2
1 449277308

result:

ok Correct

Test #14:

score: 0
Accepted
time: 5ms
memory: 1496kb

input:

81665969 919836918

output:

3
81665971 -1 -1 

result:

ok Correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 1504kb

input:

470578680 280387800

output:

2
1 470578679

result:

ok Correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 1584kb

input:

58450340 803305503

output:

2
1 58450339

result:

ok Correct

Test #17:

score: 0
Accepted
time: 5ms
memory: 1500kb

input:

125896113 323676210

output:

3
125896099 7 7 

result:

ok Correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 1500kb

input:

381905348 434752500

output:

2
1 381905347

result:

ok Correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 1472kb

input:

78916498 653897673

output:

1
78916498

result:

ok Correct

Test #20:

score: 0
Accepted
time: 5ms
memory: 1508kb

input:

35787885 270845190

output:

3
35787883 1 1 

result:

ok Correct

Extra Test:

score: 0
Extra Test Passed