所以我在有Pascal代码的地方完成了此任务,我需要弄清楚结果如何。那不是问题,因为我知道pascal,但是我需要它在1秒或更短的时间内运行,数字最大为10 ^ 9。
readln(N);
counter:=0;
for i:=N-1 downto 1 do begin
counter:= counter + 1;
if N mod i = 0 then break;
end;
writeln(counter);
这是我的代码
#include <iostream>
using namespace std;
int main()
{
int x;
int counter = 0;
cin>>x;
for (int i = 2; i <= x; i++){
if (x % i == 0){
counter = x - x / i;
break;
}
}
cout<<counter;
return 0;
}
但是它仍然不能完全获得最高分。
重述问题:1)计算F = X的最大固有因子2)输出X-F
而不是直接搜索最大的适当因子,而是应用三个琐碎的优化(也许需要更高级的方法,但是首先看看三个琐碎的优化是否足够)。
A)查找S = X的最小因子大于1。输出X-(X / S)B)特例C)偶数的特殊情况
int largest_proper_factor(int X)
{
if ( X % 2 == 0 ) return X/2; // Optimize even
// Note the add of .5 is only needed for non compliant sqrt version that
// might return a tiny fraction less than the exact answer.
int last = (int)(.5 + std::sqrt( (double) X )) );
for ( int i=3; i<=last; i+=2 ) // big savings here because even was optimized earlier
{
if ( X % i == 0 ) return X/i;
}
return 1; // special case for prime
}
[10 ^ 9之类的数字通常表示比赛问题,需要创造性的思考而不是快速的CPU ...
请参阅N mod i = 0
表示N
可被i
整除。因此,循环会在N
与其除数之一(可能加一...对其进行检查)之间计数。哪一个仍然适合您。
好吧,我得到了我想要的结果:
#include <iostream>
using namespace std;
int main()
{
int x;
int counter = 0;
cin>>x;
for (int i = 2; i <= x; i++){
if (x % i == 0){
counter = x - x / i;
break;
}
if (x / 4 == i){
i = x - 1;
}
}
cout<<counter;
return 0;
}
谢谢所有帮助我的人:)