题解 AT2554 【[ABC060B] Choose Integers】

· · 题解

原题传送门。在窝的博客中食用更佳。

【 题意概括 】

输入三个数 a，b，c，问存不存在某个倍数 i 使得 (a \times i) \mod b=c ？

若存在则输出 YES ，否则输出 NO 。

【 思路 】

直接暴力枚举，保证不超时 AWA。

但有一个问题：我们在 i 的值为多少时退出循环呢？答案是 b。证明：

令 (a \times 1) \mod b=d，则：

(a \times 2)\mod b=d \times2\mod b (a \times 3)\mod b=d \times3\mod b ... (a \times b)\mod b=(d \times b)\mod b (a \times b)\mod b=0

所以：

(a \times (b+1))\mod b=((a \times 1) \mod b+(a \times b)\mod b)\mod b (a \times (b+1))\mod b=(d+0)\mod b (a \times (b+1))\mod b=d

所以 ((a \times (b+1))\mod b) 的结果与(a \times 1) \mod b 的结果是一样的。

同理，((a \times (b+k))\mod b) 的结果与 (a \times k) \mod b

因此只需要枚举到 b 即可知道 a 以及其的倍数除 b 所得余数的所有可能了。

那么，是时候来康康代码了。

【 代码实现 + 注释 】

#include<bits/stdc++.h>//万能头文件可好 
using namespace std;
int main(){//主函数 
    int a,b,c;//定义 
    scanf("%d%d%d",&a,&b,&c);//输入 
    for(int i=1;i<=b;i++){//开始循环判断，前文有解释 
        if((a*i)%b==c){//若符合题意 
            printf("YES\n");//输出，换行是个好习惯 
            return 0;//提前结束程序 
        }
    }
    printf("NO\n");//如果一直没有符合题意的倍速，则输出NO 
    return 0;//over~
}

由于作者自愿禁言了，如果有建议请私信。否则将无法回复您哦！

完结撒花~（疯狂暗示 OoO