I think everybody must be having same problem in Problem D having time limit exceeded on Test case 15. The time limit is too strict for the problem. I am tired of optimizing it further now and I have seen exactly same logic being accepted. I am tired and frustrated now. Somebody pls tell how to optimize it from here on.↵
↵
Here is my Code:↵
↵
#pragma GCC optimize("Ofast") ↵
#pragma GCC target("avx,avx2,fma") ↵
//Somos insignificantes. Por mais que você programe sua vida, a qualquer momento tudo pode mudar.↵
// If you have God on your side,everything becomes clear↵
↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;↵
↵
const int MAX_N = 1e5 + 5;↵
const int MAX_L = 20; // ~ Log N↵
const long long MOD = 1e9 + 7;↵
const long long INF = 1e9 + 7;↵
↵
typedef long long ll;↵
typedef vector<int> vi;↵
typedef pair<int,int> ii;↵
typedef vector<ii> vii;↵
typedef vector<vi> vvi;↵
#define fi first↵
#define popcount(x) __builtin_popcountll(x)↵
#define se second↵
#define LSOne(S) (S & (-S))↵
#define isBitSet(S, i) ((S >> i) & 1)↵
const int MAXN=2e7+10;↵
ll spf[MAXN]; ↵
↵
// Calculating SPF (Smallest Prime Factor) for every ↵
// number till MAXN. ↵
// Time Complexity : O(nloglogn) ↵
void sieve() ↵
{ ↵
spf[1] = 1; ↵
for (int i=2; i<MAXN; i++) ↵
↵
// marking smallest prime factor for every ↵
// number to be itself. ↵
spf[i] = i; ↵
↵
// separately marking spf for every even ↵
// number as 2↵
void sieve() ↵
{ ↵
spf[1] = 1; ↵
for (int i=2; i<MAXN; i++) ↵
↵
↵
spf[i] = i; ↵
↵
↵
for (int i=4; i<MAXN; i+=2) ↵
spf[i] = 2; ↵
↵
for (int i=3; i*i<MAXN; i++) ↵
{ ↵
// checking if i is prime ↵
if (spf[i] == i) ↵
{ ↵
// marking SPF for all numbers divisible by i ↵
for (int j=i*i; j<MAXN; j+=i) ↵
↵
// marking spf[j] if it is not ↵
// previously marked↵
if (spf[j]==j) ↵
spf[j] = i; ↵
} ↵
} ↵
} ↵
long long binpow(long long a, long long b) {↵
↵
long long res = 1;↵
while (b > 0) {↵
if (b & 1)↵
res = res * a ;↵
a = a * a ;↵
b >>= 1;↵
}↵
res=res;↵
return res;↵
}↵
ll p2[35];↵
ll getFactorization(ll x) ↵
{ ↵
//vector<ll> ret;↵
map<ll,ll>bo;↵
ll sz=0; ↵
while (x != 1) ↵
{ ↵
if(bo[spf[x]]==0){↵
sz++;↵
bo[spf[x]]=1;↵
}↵
//ret.push_back(spf[x]); ↵
x = x / spf[x]; ↵
} ↵
↵
return sz; ↵
} ↵
ll f(ll num){↵
ll req=getFactorization(num);↵
//ll l=req.size();↵
return p2[req] ;↵
}↵
↵
↵
↵
void solve() {↵
ll c,d,n;↵
cin>>c>>d>>n;↵
ll ans=0;↵
//map<ll,ll>mp;↵
for(ll j=1;j*j<=n;j++){↵
if(n%j==0){↵
ll p1=j;↵
ll p2=n/j;↵
ll r1=n/p1 +d;↵
ll r2=n/p2+d;↵
if(r1%c==0){↵
ans+=f(r1/c);↵
↵
}↵
if(r1!=r2){↵
if(r2%c==0){↵
ans+=f(r2/c);↵
↵
}↵
↵
}↵
}↵
}↵
cout<<ans<<endl; ↵
↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
↵
#ifdef LOCAL↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
sieve();↵
ll pj=1;↵
for(ll i=0;i<=34;i++){↵
p2[i]=pj;↵
pj=pj*2;↵
} ↵
int tc; cin >> tc;↵
for (int t = 1; t <= tc; t++) {↵
//cout << "Case #" << t << ": ";↵
solve();↵
}↵
}
↵
Here is my Code:↵
↵
#pragma GCC optimize("Ofast") ↵
#pragma GCC target("avx,avx2,fma") ↵
// If you have God on your side,everything becomes clear
↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#include <ext/pb_ds/tree_policy.hpp>↵
↵
using namespace std;↵
using namespace __gnu_pbds;↵
↵
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;↵
↵
const int MAX_N = 1e5 + 5;↵
const int MAX_L = 20; // ~ Log N↵
const long long MOD = 1e9 + 7;↵
const long long INF = 1e9 + 7;↵
↵
typedef long long ll;↵
typedef vector<int> vi;↵
typedef pair<int,int> ii;↵
typedef vector<ii> vii;↵
typedef vector<vi> vvi;↵
#define fi first↵
#define popcount(x) __builtin_popcountll(x)↵
#define se second↵
#define LSOne(S) (S & (-S))↵
#define isBitSet(S, i) ((S >> i) & 1)↵
const int MAXN=2e7+10;↵
ll spf[MAXN]; ↵
↵
// number till MAXN. ↵
// Time Complexity : O(nloglogn) ↵
void sieve() ↵
{ ↵
spf[1] = 1; ↵
for (int i=2; i<MAXN; i++) ↵
↵
// marking smallest prime factor for every ↵
// number to be itself. ↵
spf[i] = i; ↵
↵
// separately marking spf for every even ↵
// number as 2
void sieve() ↵
{ ↵
spf[1] = 1; ↵
for (int i=2; i<MAXN; i++) ↵
↵
↵
spf[i] = i; ↵
↵
↵
for (int i=4; i<MAXN; i+=2) ↵
spf[i] = 2; ↵
↵
for (int i=3; i*i<MAXN; i++) ↵
{ ↵
if (spf[i] == i) ↵
{ ↵
for (int j=i*i; j<MAXN; j+=i) ↵
↵
// previously marked
if (spf[j]==j) ↵
spf[j] = i; ↵
} ↵
} ↵
} ↵
long long binpow(long long a, long long b) {↵
↵
long long res = 1;↵
while (b > 0) {↵
if (b & 1)↵
res = res * a ;↵
a = a * a ;↵
b >>= 1;↵
}↵
res=res;↵
return res;↵
}↵
ll p2[35];↵
ll getFactorization(ll x) ↵
{ ↵
//vector<ll> ret;↵
map<ll,ll>bo;↵
ll sz=0; ↵
while (x != 1) ↵
{ ↵
if(bo[spf[x]]==0){↵
sz++;↵
bo[spf[x]]=1;↵
}↵
//ret.push_back(spf[x]); ↵
x = x / spf[x]; ↵
} ↵
↵
return sz; ↵
} ↵
ll f(ll num){↵
ll req=getFactorization(num);↵
//ll l=req.size();↵
return p2[req] ;↵
}↵
↵
↵
↵
void solve() {↵
ll c,d,n;↵
cin>>c>>d>>n;↵
ll ans=0;↵
//map<ll,ll>mp;↵
for(ll j=1;j*j<=n;j++){↵
if(n%j==0){↵
ll p1=j;↵
ll p2=n/j;↵
ll r1=n/p1 +d;↵
ll r2=n/p2+d;↵
if(r1%c==0){↵
ans+=f(r1/c);↵
↵
}↵
if(r1!=r2){↵
if(r2%c==0){↵
ans+=f(r2/c);↵
↵
}↵
↵
}↵
}↵
}↵
cout<<ans<<endl; ↵
↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(0);↵
cin.tie(0); cout.tie(0);↵
↵
#ifdef LOCAL↵
freopen("input.txt", "r", stdin);↵
freopen("output.txt", "w", stdout);↵
#endif↵
sieve();↵
ll pj=1;↵
for(ll i=0;i<=34;i++){↵
p2[i]=pj;↵
pj=pj*2;↵
} ↵
int tc; cin >> tc;↵
for (int t = 1; t <= tc; t++) {↵
//cout << "Case #" << t << ": ";↵
solve();↵
}↵
}
