abc 361 F — x = a^b

Revision en1, by T_C_D, 2024-07-16 15:34:54

Can someone help me with this problem [](http:://atcoder.jp/contests/abc361/tasks/abc361_f) Out of 76 test cases, only 4 are incorrect, but I don't know what is wrong with my solution. The idea of my solution is to use the inclusion-exclusion principle.

 #include <bits/stdc++.h>
 using namespace std;
 #define Try ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout << std::setiosflags(std::ios::fixed) << 
 std::setprecision(40);
 #define dd long double
 #define endl "\n"
 ////#define ll long long
 #define ll unsigned long long
 #include <ext/pb_ds/assoc_container.hpp>
 #include <ext/pb_ds/tree_policy.hpp>
 using namespace __gnu_pbds;
 typedef tree<ll, null_type,less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const long long INF =1e18;

dd nthRoot(dd x,dd n) {
    return pow(x, 1.0 / n);
}


ll inclusion_exclusion(vector<ll>&toto,ll res,ll k){
    ll odd=0;
    ll even=0;
    for(ll i=1;i<(1<<k);i++){
        ll p=1;
        bool test=true;
        for(ll j=0;j<k;j++){
            if((1<<j)&i) {
                if(p>INF){
                    test=false;
                    break;
                }
                p*=toto[j];
            }
        }
        if(!test) continue;
        ll nbr=__builtin_popcountll(i);
        if(nbr%2) odd+=nthRoot(res,p);
        else even+=nthRoot(res,p);
    }
    return odd-even;
}

bool est_premier(ll n){
     if(n<=1) return false;
     if(n<=3) return true;
     for(ll i=2;i*i<=n;i++) {
        if(n%i==0) return false;
     }
     return true;
}
void sol() 
{
   vector<ll> prim;
   for(ll i=2;i<=61;i++){
      if(est_premier(i)) prim.push_back(i);
   }
   ll n;cin>>n;
   ////aff(prim);
   if(n==1){
       cout<<1<<endl;
       return;
   }
   ll ans=sqrt(n);
   vector<ll> toto={2};
   ll k=1;
   for(ll i=1;i<17;i++){
      ll res=nthRoot(n,prim[i]);
      if(res==1) break;
      ans+=(res-inclusion_exclusion(toto,res,k));
      toto.push_back(prim[i]);
      k++;
   }
   cout<<ans<<endl;
}
signed main() {
    Try
    ll ttt= 1;
    while (ttt--) {
        sol();
    }
    return 0;
}

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English T_C_D 2024-07-16 15:34:54 2208 Initial revision (published)