P7933 [COCI2007-2008#5] PASCAL

· · 题解

题目：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;
}