目錄
- 題目大意
- 解題思路
- AC代碼
題目大意
給你一個數n，你可以找一些大于1的整數a和b，如果 c = a b < n c=a^{b}<n c=ab<n，那么 c c c就是一個“可展開數”，
問1~n的“不可展開數”有多少，
解題思路
2 34 = 17 , 179 , 869 , 184 > 10 , 000 , 000 , 000 2^{34}=17,179,869,184>10,000,000,000 234=17,179,869,184>10,000,000,000，也就是說1e10范圍內以2為底的符合條件的數不到35個，當底數增加的10時，1e10范圍內以10為底的符合條件的數剩下不到10個，總之，可展開數比不可展開數少，
(樣例2中100000范圍內有99634個不可展開數也能看出可展開數很少)，我們只需要計算出可展開數的個數，就可計算出答案，
在計算可展開數的個數時，需要注意到，b>2，
而 n \sqrt{n} n ?的平方已經等于n了，顧當底數大于 n \sqrt{n} n ?時，底數就不再需要增加了，即使為1e10的數，底數的列舉范圍也只是2~1e5，在時間允許范圍內，
AC代碼
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
map<ll, bool> mp; //防止重復計算
int main()
{
ll n, s = 0;
cin >> n;
ll k = sqrt(n);
for (ll a = 2; a <= k; a++) //底數從2列舉到√n
{
ll b = 2; //指數從2開始列舉
while (1)
{
ll c = pow(a, b);
if (c > n) //當a^b大于n時，結束回圈
break;
if (!mp[c]) //如果還沒有出現過
{
mp[c] = 1; //記錄下這個可展開數
s++;
}
b++;
}
}
printf("%lld\n", n - s);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/264574.html
標籤：其他