题解 B2043 【判断能否被 3，5，7 整除】

囧仙 · 2021-07-03 21:47:07 · 题解

题解

观察发现， 3,5,7 恰好为公差为 2 的等差数列。所以我们为什么不能用循环来枚举呢？

本题还有一个很好的性质：如果 n 能被 x 整除（x\in\{3,5,7\}），那么必然要输出 x 加上一个空格。于是我们并不需要同时判断 n 能否被三个数整除、并不需要枚举其中两个数看看能否整除等。本质上已经把判断语句的数目简化为 3 了，加上一句循环可以再次减少码量。

顺便挂两个在本题没啥用，但以后或许有用的性质：

• 一个数能被 3 整除，当且仅当它的十进制下每一位的和能被 3 整除。证明如下：

  n=\sum_{i=0}^k x_i\cdot 10^i\equiv \sum_{i=0}^k x_i\cdot (10^i\bmod 3)\equiv \sum_{i=0}^k x_i \pmod 3

  其中， x_i 表示 n 在十进制下每一位的值， k 是 n 的位数。

• 一个数能被 5 整除，当且仅当它的十进制下最后一位是 0 或者 5 。同样可以用 3 的结论来证明，因为 i>0 时 10\equiv 0\pmod 5 ，于是只要看最后一位。而最后一位能被 5 整除，显然只能是 0 或 5 。

参考代码

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
    cin>>n; for(int i=3;i<=7;i+=2) if(n%i==0) printf("%d ",i); 
    return 0;
}