# 【TopCoder】[TCO2013 2A] The Powers

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 32000;

int vis[N],pri[N],tot;
LL ans[40];
vector<int> que;

class ThePowers{
public:
long long find(LL A, LL B) {
prework(N-1, B); LL ret = B - 1;
for (LL r=2,t,vi;r*r<=A;r++) {
if (judge(r)) {
for (t=0,vi=r;vi<=A;t++,vi*=r);
ret += t * B - ans[t];
}
}
return (LL)A * B - ret;
}
private:
LL DFS(LL t, LL B, LL cnt, LL lcm) {
if (!t) {
if (cnt & 1) return (LL)B / lcm;
else if (cnt) return -(LL)B / lcm;
else return 0;
} else {
return
DFS(t-1, B, cnt, lcm) +
DFS(t-1, B, cnt+1, lcm / Gcd(lcm, que[t-1]) * que[t-1]);
}
}
inline void prework(LL n, LL B) {
for (int i=2;i<=n;i++) {
if (!vis[i]) vis[i] = i, pri[++tot] = i;
for (int j=1;j<=tot&&pri[j]*i<=n;j++) {
vis[i*pri[j]] = pri[j];
if (i % pri[j] == 0) break;
}
}
for (int i=1;i<30;i++) {
for (int j=1;j<=i;j++) {
que.clear();
for (int k=j,tag=0;k<=i;k++,tag=0) {
for (int l=que.size()-1;l>=0;l--)
if (k % que[l] == 0)
{tag = 1; break;}
if (!tag) que.push_back(k);
}
ans[i] += DFS(que.size(), j * B, 0, 1);
ans[i] -= DFS(que.size(), j * B - B, 0, 1);
}
cout<<ans[i]<<endl;;
}
}
inline LL Gcd(LL a, LL b) {
return b? Gcd(b, a%b): a;
}
inline bool judge(int w) {
int GCD = 0;
for (int t=0,p=vis[w];w>1;t=0,p=vis[w]) {
while (w % p == 0) t++, w /= p;
if (!GCD) GCD = t;
else GCD = Gcd(GCD, t);
}
return GCD == 1;
}
};


## 2 thoughts to “【TopCoder】[TCO2013 2A] The Powers”

1. Hey this is somewhat of off topic but I was wanting to know if blogs use WYSIWYG editors or if you have to manually code with HTML. I’m starting a blog soon but have no coding expertise so I wanted to get advice from someone with experience. Any help would be enormously appreciated!

2. I have been absent for some time, but now I remember why I used to love this website. Thanks, I?¦ll try and check back more often. How frequently you update your web site?