网站权重降低,网站搭建教程零基础,网站建设优化哪家好,运城门户网站建设正题 题目大意
给出nnn#xff0c;求[1..n][1..n][1..n]中有多少个数可以被ab(b1)a^b(b1)ab(b1)表示 解题思路
首先如果bbb等于222#xff0c;那么可以被表示的数就是n\sqrt nn个 bbb不是质数时#xff0c;显然所以的数都可以被一个bbb是质数的情况表示。
…正题 题目大意
给出nnn求[1..n][1..n][1..n]中有多少个数可以被ab(b1)a^b(b1)ab(b1)表示 解题思路
首先如果bbb等于222那么可以被表示的数就是n\sqrt nn个
bbb不是质数时显然所以的数都可以被一个bbb是质数的情况表示。
当bbb大于等于三时aaa的个数级别不超过10610^6106所以我们枚举后面的数。
需要考虑重复如43824^38^24382其实这个重复本质上就是(22)3(23)2(2^2)^3(2^3)^2(22)3(23)2也就是说如果aaa可以表示为kq(qb)k^q(qb)kq(qb)时那么aba^bab一定已经被计算过了 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
#includemap
#define ll long long
using namespace std;
ll n,ans;
bool v[100],M[1000100];
int main()
{scanf(%lld,n);ans(long long)(sqrt(1.0*n));for(ll i1;i*i1e6;i)M[i*i]1;for(ll i2;i64;i){if(v[i])continue;for(ll ji;j64;ji)v[j]1;if(i2)continue;ll k1,z;for(;pow(k,i)n;k)if(!M[k])ans;for(k1;(zpow(k,i))n;k)if(z1e6)M[z]1;else break;}printf(%lld,ans);
}
