[思维]ACM-T1-余数研究

题面题目描述输入格式输出格式一句话题面 思路分析暴力思路一点优化正解分析推数据样例数据普遍数据 正解 完整代码

题面

题目描述

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

输入格式

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

输出格式

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

一句话题面

给定$n$,$k$ （$n$,$k\le 10^{18}$）

回答$n\%i,i\in [1,k]$是否都不同

思路分析

暴力思路

枚举$1$~$k$，看看余数是否相同 但是TLE是少不了的

一点优化

当$N\le K$时，直接No 因为$N\%1=0$ $N\%N=0$ 但还是TLE，分数也不变 ^{一分都没多讲了有什么用啊}

正解分析

推数据

样例数据

5 3—Yes

$5\%1=0$$5\%2=1$$5\%3=2$

好像有点规律 再来一组 5039 7—Yes

$5039\%1=0$$5039\%2=1$$5039\%3=2$$5039\%4=3$$5039\%5=4$$5039\%6=5$$5039\%7=6$

好像真有规律

普遍数据

N K—Yes$(N<K)$

算式可取余数$N\%1=\in [0,0]$0$N\%2=\in [0,1]$0,1$N\%3=\in [0,2]$0,1,2$N\%4=\in [0,3]$0,1,2,3$\dots \dots$$\dots \dots$$N\%K=\in [0,K-1]$0,1,2,$\dots \dots$,K-2,K-1

可以通过普遍的数据看出 如果回答是Yes,那么$N\%i=i-1$($i\in [1,K]$)

正解

$$question：“NK"=\{\begin{array}{rl}ans& =“Yes”(N\%i=i-1(i\in [1,K]))\\ ans& =“No”(N\%i\ne i-1(i\in [1,K]))\end{array}$$

完整代码

#include<bits/stdc++.h> using namespace std; long long N,K; bool ans; int main(){ while(1){ ans=1; scanf("%lld%lld",&N,&K); if(N==0&&K==0)return 0; for(long long i=1;i<=K;i++){ if(N%i!=i-1) { ans=0; break; } } if(ans)printf("Yes\n"); else printf("No\n"); } }