Problem D Educational Round 106
Difference between en1 and en2, changed 558 character(s)
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();↵
    }↵
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English dominator1234 2021-03-18 21:54:05 2781 Tiny change: ' p2[35];\nll getFa' -> ' p2[35];\n \nll getFa'
en3 English dominator1234 2021-03-18 21:43:28 55
en2 English dominator1234 2021-03-18 21:38:50 558
en1 English dominator1234 2021-03-18 21:37:36 3698 Initial revision (published)