CF922C Cave Painting 题解 （作业）

题面

题目描述

输入 $n$ 和 $k$，判断 $n$ $mod$ $1$ ~ $k$ 每个数的余数是不是都不相同

输入

输入数据包含多组，每行两个数字 $n$、$k$，空格隔开。 以$0$ $0$结束

输出

对于每行的有效数据，如果所有余数均不相同，输出 $Yes$，否则输出 $No$

样例输入

4 4 5 3 0 0

样例输出

No Yes

提示

说明/提示 $n,k\le 10^{18}$ 【样例解释】 对于 $4$ $4$ 由于 $4$ $mod$ $1$ 和 $4$ $mod$ $2$ 都是 $0$，所以是 $No$ 对于 $5$ $3$ 由于 $5$ $mod$ $1=0$ $5$ $mod$ $2=1$ $5$ $mod$ $3=2$ 所以余数各不相同，输出$Yes$

---

题目分析

输入 $n$ 和 $k$，判断 $n$ $mod$ $1$ ~ $k$ 每个数的余数是不是都不相同

我们将这段话分析后，会发现： $n$ $mod$ $1=0$ 为保证每个数的余数都不相同，就需要 $n$ $mod$ $2=1$ 以此类推： $n$ $mod$ $3=2$ $n$ $mod$ $4=3$ $n$ $mod$ $5=4$ …… $n$ $mod$ $i=i-1$ 也就是说 $(n+1)$ $mod$ $i=0$ $(1\le i\le k)$ 然后我们可以发现，这个数必须是 $k!$ 的倍数 $-1$，而 $20!$ 就已经爆 $long$ $long$ 了，所以当 $k>20$ 或 $k\ge n$ 时肯定不能满足条件 （我乱讲的） ，所以可以排除。

code

#include<cstdio> #include<iostream> #include<algorithm> using namespace std; long long n,k,p; bool flag; int main(){ int i; while(1){ flag=0; scanf("%lld%lld",&n,&k); if(!n&&!k) return 0; if(k>20){ printf("No\n"); continue; } p=1; for(i=1;i<=k;i++) if(n%i!=i-1){ flag=1; printf("No\n"); break; } if(flag==0) printf("Yes\n"); } }