自动搬运

查看原文

来自洛谷，原作者为

	eEfiuys 你了我了，大家都了

搬运于2025-08-24 22:34:26，当前版本为作者最后更新于2021-11-10 22:19:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目：P7933

如果你会 Pascal，那么只需要加上头和尾就行了。然鹅，作为 c++ 党，首先要将其翻译成 c++ 语言。方式：自己理解、bdfs 等（大雾

好吧，先翻译成汉语：

readln(N); //输入N
counter := 0; //counter从0开始
for i := N-1 downto 1 do begin //i从N-1循环到1，一次循环开始
	counter := counter + 1; //counter加1
	if N mod i = 0 then break; //如果N模i等于0，那么跳出循环
end; //一次循环结束
writeln(counter); //输出counter

注：以下的 $n$ 指 $N$，$cnt$ 指 $counter$。

翻译成 c++ 语言就是：

#include<iostream>
using namespace std;
int main(){
    int n,cnt=0;
    cin>>n;
    for(int i=n-1;i>=1;i--){
        cnt++;
        if(n%i==0)break;
    }
    cout<<cnt;
    return 0;
}

可是，$1 \leq n \leq 10^9$，显然 TLE。考虑一下，跳出循环的地方就是除 $n$ 以外最大的因数。

因此，我们从 $2$ 到 $\sqrt n$ 枚举，将范围内最小的因数记为 $m$。如果 $m > \sqrt n$，说明 $n$ 为质数，结果为 $n-1$。否则会在 $n/m$ 跳出循环，结果为 $n-\dfrac{n}{m}$。

#include<iostream>
using namespace std;
int main(){
    int n,m;
    cin>>n;
    for(m=2;m*m<=n&&n%m;m++);
    if(m*m>n)cout<<n-1;
    else cout<<n-n/m;
    return 0;
}