### Sukarna_Paul's blog

By Sukarna_Paul, history, 8 months ago, ,

Here is my solution :

#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<bits/stdc++.h>
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define pli pair<long long , int>
#define pil pair<int ,long long>
#define pi acos(-1)
#define pb push_back
#define mkp make_pair
#define all(a) a.begin(), a.end()
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define MAX 300005
#define INF 0x3f3f3f3f
template <class T> inline T bigmod(T p,T e,T M){ll ret = 1LL;for(; e > 0LL; e >>= 1LL){if(e & 1LL) ret = (ret * p) % M;p = (p * p) % M;}return (T)ret;}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}   // M is prime}
using namespace std;

vector <ll> prime;
bitset <100000010> bs;

void sieve ()
{
bs.set ();
prime.pb(2LL);
for (ll i = 3; i < 100000000; i+=2)
{
if (bs[i])
{
prime.pb(i);
for (ll j = i * i; j < 10000000; j += i+i)
{
bs[j] = 0;
}
}
}
}

int main(){
IOS
//freopen("output.txt","w",stdout);
sieve();
int i=0;
unordered_map<int,int>r,c;

for(auto it=prime.begin();it!=prime.end();){
i++;
for(int j=1;j<=i;j++){
r[(*it)]=i;
c[(*it)]=j;
it++;
}
}
int t;
cin>>t;
for(int i=0;i<t;i++){
int a;
cin>>a;
if(r[a]==0){
cout<<"-1"<<endl;
continue;
}
cout<<r[a]<<" "<<c[a]<<endl;

}
}


• 0

 » 8 months ago, # |   0 Maybe this can help. https://codeforces.com/blog/entry/54090
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Ok thanks , let me see
 » 8 months ago, # |   0 Reading the comments in SPOJ, it seems the time limit is a bit strict (classic SPOJ). So, regardless of the sieve implementation, something that may help in this case is changing to "\n".I understand that flushes the buffer every time.If you want to test correctness there seems to be a tutorial version after the examples.Happy Coding!
•  » » 8 months ago, # ^ |   0 Sorry , but it didn't work . Still TLE :(
 » 8 months ago, # |   0 You may try to use Segmented Sieve which is claimed to have less cache memory misses when n is large.