2021 年百度之星·程序设计大赛 - 初赛一Problem 1004 萌新

problem Description

给定两个正整数 a,b，求最小和最大的 c 满足 a mod c=b mod c，满足 c-1 为正整数，且 c≤max(a,b)。

思路

正整数a，b除以c有相同的余数，则可得 a - b=c*x（这里假定a>=b），则最大的c即x=1时，c=a-b,最小的c为a-b的最小因数。因为c-1要满足为正整数，即c>=2,所以当a-b=1时无解。
由于要找出a-b的最小因数，因此需提前计算1-32000（根号1e9）内的所有质数。

const int maxn=32000;
int prime[maxn];
int prime_sum=0;
void prime_init(){bool visit[maxn];memset(visit,1,sizeof(visit));visit[1]=0;for(int i=2;i<maxn;i++){if(visit[i]){prime[++prime_sum]=i;for(int j=i*i;j<maxn;j+=i) visit[j]=0;}}
}

这里要加一个特判，即当a=b时，如果a=b=1，此时无解输出-1，其它情况输出2与a。

代码

int main(){prime_init();int T;scanf("%d",&T);while(T--){int a,b;scanf("%d%d",&a,&b);if(a<b) swap(a,b);int t=a-b;if(t==1) printf("-1 -1\n");else{if(a==b){if(a==1) printf("-1 -1\n");else printf("2 %d\n",a);}else{int temp=t;for(int i=1;i<=prime_sum;i++){if(prime[i]>t) break;if(t%prime[i]==0){temp=prime[i];break;}}printf("%d %d\n",temp,t);}}}return 0;
}

end

这是我在CSDN发的第一篇博客，主要是想记录自己的学习刷题过程，本人目前也只是一个弱校在读大学生，如文章有所错误欢迎指出交流，感谢阅读。