学习C++从娃娃抓起！记录下AtCoder（日本算法竞技网站）备赛学习过程中的题目，记录每一个瞬间。
附上汇总贴：AtCoder 备赛刷题 | 汇总
【Problem Statement】
How many integers x x x between 1 1 1 and N N N, inclusive, can be expressed as x = a b x=a^b x=ab using some positive integer a a a and a positive integer b b b not less than 2 2 2?
有多少个介于 1 1 1 和 N N N 之间的整数 x x x（包括在内）可以用一些正整数 a a a 和一个不小于 2 2 2 的正整数 b b b 表示为 x = a b x=a^b x=ab？
【Constraints】
- All input values are integers.
- 1 ≤ N ≤ 1 0 18 1≤N≤10^{18} 1≤N≤1018
【Input】
The input is given from Standard Input in the following format:
N
【Output】
Print the answer as an integer.
【Sample Input 1】
99
【Sample Output 1】
12
The integers that satisfy the conditions in the problem statement are 1 , 4 , 8 , 9 , 16 , 25 , 27 , 32 , 36 , 49 , 64 , 81 1,4,8,9,16,25,27,32,36,49,64,81 1,4,8,9,16,25,27,32,36,49,64,81: there are 12 12 12.
【Sample Input 2】
1000000000000000000
【Sample Output 2】
1001003332
【代码详解】
《AtCoder x = a^b》 #数学# #枚举#
#include <bits/stdc++.h>
using namespace std;
#define int long long
int mu[100], pri[100], pre[100], cnt;
int n, ans;
bool zs[100];
void calc()
{
zs[1] = true;
mu[1] = 1;
for (int i=2; i<100; i++)
{
if (!zs[i]) pri[cnt++] = i, mu[i] = -1;
for (int j=0; pri[j]*i<100; j++) // 线性筛模板
{
zs[i*pri[j]] = true;
if (i%pri[j]) mu[i*pri[j]] = -mu[i];
else
{
mu[i*pri[j]]=0;
break;
}
}
}
}
int qmi(int a, int b) // 快速幂模板
{
int mul = 1;
while (b)
{
if (b&1) mul *= a;
a = a * a;
b >>= 1;
}
return mul;
}
int Sqrt(int n, int k)
{
int l=1, r = pre[k];
int ret = 1;
while (l<r) // 二分模板
{
int mid = (l+r+1)>>1;
if (qmi(mid, k)<=n) l = mid;
else r = mid-1;
}
return l;
}
signed main()
{
calc();
cin >> n;
for (int i=2; i<=60; i++)
if (mu[i]!=0)
pre[i] = (int)pow(1ll<<61, 1.0/i);
for (int i=2; i<=60; i++)
if (mu[i]!=0)
ans -= mu[i]*(Sqrt(n,i)-1);
cout << ans+1;
return 0;
}
【运行结果】
99
12