Problem D Educational Round 106

Правка en3, от dominator1234, 2021-03-18 21:43:28

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")

#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, 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 vi; typedef pair<int,int> ii; typedef vector vii; typedef vector 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];

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) 


            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 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();
}

}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский dominator1234 2021-03-18 21:54:05 2781 Tiny change: ' p2[35];\nll getFa' -> ' p2[35];\n \nll getFa'
en3 Английский dominator1234 2021-03-18 21:43:28 55
en2 Английский dominator1234 2021-03-18 21:38:50 558
en1 Английский dominator1234 2021-03-18 21:37:36 3698 Initial revision (published)