### T_C_D's blog

By T_C_D, history, 3 weeks ago,

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


• +1

 » 3 weeks ago, # |   0 i dont have any idea but i upvote
 » 3 weeks ago, # |   +6 I think the problem is due to the precision of the pow function