Oto zatwierdzona przez PA wersja, i tak już po terminie wiec chyba problemu nie będzie
Ta zatwierdzona wersja daje kompletny chrzan dla liczb blizkich górnej granicy 500mln - którą widać w zadaniu.
- Mój pomysł z rozkładem na liczby pierwsze był słuszny (dla dużych liczb) nie chce mi się tego sprawdzać dla małych zakresów.
#include <iostream>
#include <iomanip>
#include <list>
#include <set>
#include <cmath>
using namespace std;
class Primes
{
private:
list<long long> List;
struct Data
{
long long V;
list<long long>::iterator it;
Data(long long V,list<long long>::iterator it):V(V),it(it) {}
bool operator<(const Data &D)const { return V<D.V; }
};
multiset<Data> Set;
long long N;
public:
Primes():N(2) {}
long long next();
};
long long Primes::next()
{
long long Ret=N;
for(bool Stop=false;!Stop;N+=1+(N>2))
{
Stop=true;
multiset<Data>::iterator s=Set.begin();
while((s!=Set.end())&&(s->V<=N))
{
if(s->V==N) Stop=false;
Data d=*s;
d.V+=2*(*(d.it));
Set.erase(s);
Set.insert(d);
s=Set.begin();
}
if(Stop) Set.insert(Data(3*N,List.insert(List.end(),Ret=N)));
}
return Ret;
}
int main()
{
for(long long N=500000000LL;N>490000000LL;--N)
{
cout<<setw(20)<<N;
Primes Pr;
long long n=N,mul=1,p=1;
while((n>1)&&(p*p<n))
{
p=Pr.next();
bool use=false;
while(!(n%p)) { n/=p; use=!use; }
if(use) mul*=p;
}
cout<<setw(20)<<N*n*mul;
long long wynik=2*N;
for(long double pierw=sqrt(wynik);pierw!=(long long)pierw;pierw=sqrt(wynik=wynik+N)) ;
cout<<setw(20)<<wynik<<endl;
}
return 0;
}