网站设计展示,asp网站配色,wordpress如何清空,wordpress easy stmpHDU - 2204 Eddy’s爱好
题意#xff1a;
给你一个正整数N#xff0c;确定在1到N之间有多少个可以表示成M^K#xff08;K1)的数
题解#xff1a;
参考题解#xff1a; 我们先举例找找规律 1~10以内2的次方有多少个#xff1f;有121,224,329,一共三个#xff0c;…HDU - 2204 Eddy’s爱好
题意
给你一个正整数N确定在1到N之间有多少个可以表示成M^KK1)的数
题解
参考题解 我们先举例找找规律 1~10以内2的次方有多少个有121,224,329,一共三个10开方(向下取整)为3 也就是1~n之间k次方数有多少个 等于n(1/k)这算是个结论其实 如果我们直接按这个计算会发现有很多重复比如有个数是2的次方也有可能是4的次方也有可能是6的次方但是这些其实在2的次方中就已经计算了而48是2的倍数所以我们只需要管素数次方就行了一个2就涵盖了所有468等等。你也可以这么理解如果M(ab)也可以写成(Ma)b如果指数不是质数那么一定可以每另外一组数字表示且这组数字的指数是质数。所以说我们只需要统计指数是质数的数字能够组成多少个n以内的数字。 那是不是这样就没有重复了也不是不同数之间有可能也有就比如一个数是6的次方他就被素数2次方和素数3次方同时给统计了这个要用到容斥比如272和93会重复是因为他们都能凑出指数6所以我们需要减去指数6所得到的个数 举个例子 n729 指数为222,32,42,52,62…272 指数为323,33,43,53,63…93 8226和4326就是重复的我们用n计算出指数为6的个数729(1/6)1,那么答案就是先指数为2的再指数为3的最后减指数为6的这是容斥为2的情况 如果重复的是235的共同倍数30同理235- 2 * 3 -3 * 5 - 2 * 5 2 * 3 * 5(结合下图应该能明白)这是容斥的层数为3的情况 那容斥为4的情况呢题目说了n在1e18的范围内说明mk,k取值要小于61而2 * 3 * 5612 * 3 * 5 * 7所以容斥四层的情况不用考虑
代码
#includebits/stdc.h
#define debug(a,b) printf(%s %d\n,a,b);
typedef long long ll;
using namespace std;inline int read(){int s0,w1;char chgetchar();while(ch0||ch9){if(ch-)w-1;chgetchar();}while(ch0ch9) ss*10ch-0,chgetchar();//s(s3)(s1)(ch^48);return s*w;
}
int p[]{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61};
int main()
{ll n;while(cinn){ll ans1;ll tmp;for(int i0;;i){tmp(ll)pow(n,1.0/p[i]);if(tmp2)break;//说明n开p[i]次方不足 anstmp-1;for(int ji1;;j){tmp(ll)pow(n,1.0/p[i]/p[j]);if(tmp2)break;ans-tmp-1;for(int kj1;;k){tmp(ll)pow(n,1.0/p[i]/p[j]/p[k]);if(tmp2)break;anstmp-1;} } }coutansendl;}return 0;
}
