HDU 2204 Eddy's爱好（容斥原理dfs写法）题解-白红宇

HDU 2204 Eddy's爱好（容斥原理dfs写法）题解

阅读量：5760 次

发布时间：2019-06-18

本文共 2561 字，大约阅读时间需要 8 分钟。

题意：定义如果一个数能表示为M^k，那么这个数是好数，问你1~n有几个好数。

思路：如果k是合数，显然会有重复，比如a^(b*c) == (a^b)^c，那么我们打个素数表，指数只枚举素数，2^60 > 1e18，所以打60以内素数就够了。但是显然指数为素数依然会有重复的，比如（a^b）^c == (a^c)^b，这里就要用到容斥了。我们如果用一个数组a[i]表示指数为第i个素数的数的个数，那么最终答案应该是，加上一个的，减去两个的，加上三个的（因为2 * 3 * 5 * 7 > 60，最多只能有三个相乘形成指数）。如果我要算出指数为p的这样的数有几个，那么可以计算pow(n,1.0/p)。先写了一个朴素版的，纯枚举；后来又写了一个dfs的，这样大于3也能用了。

讲一些小细节，每次算出个数我们都减去1这里是去掉了1^p，我们在最后答案加上1。最后一个样例答案是“1001003332”，我的“1001003331”但是过了。

容斥：对于几个集合求解并集大小，那么采用一种方法：加上所有单个集合，减去所有两个集合相并部分，加上所有三个集合相并部分，减去所有四个集合相并部分.....

参考：

代码：

/*朴素写法1*/#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long longusing namespace std;const int maxn = 20000 + 10;const int seed = 131;const int MOD = 1000000000 + 7;const int INF = 0x3f3f3f3f;int prime[70], p[70], pn;ll ans, n;void get(){ memset(p, 0, sizeof(p)); pn = 0; for(int i = 2; i <= 60; i++){ if(!p[i]){ prime[pn++] = i; for(int j = i * i; j <= 60; j += i){ p[j] = 1; } } }}int main(){ get(); while(~scanf("%lld", &n)){ ans = 0; ll ret; for(int i = 0; i < pn; i++){ ret = pow((double)n, 1.0 / prime[i]); if(ret == 1) break; ans += ret - 1; } for(int i = 0; i < pn; i++){ for(int j = i + 1; j < pn; j++){ ret = pow((double)n, 1.0 / (prime[i] * prime[j])); if(ret == 1) break; ans -= ret - 1; } } for(int i = 0; i < pn; i++){ for(int j = i + 1; j < pn; j++){ for(int k = j + 1; k < pn; k++){ ret = pow((double)n, 1.0 / (prime[i] * prime[j] * prime[k])); if(ret == 1) break; ans += ret - 1; } } } printf("%lld\n", ans + 1); } return 0;}

/*dfs写法*/#include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #define ll long longusing namespace std;const int maxn = 20000 + 10;const int seed = 131;const int MOD = 1000000000 + 7;const int INF = 0x3f3f3f3f;int prime[60], p[70], pn;ll ans, n, flag;void get(){ memset(p, 0, sizeof(p)); pn = 0; for(int i = 2; i <= 60; i++){ if(!p[i]){ prime[pn++] = i; for(int j = i * i; j <= 60; j += i){ p[j] = 1; } } }}void dfs(int start, int p, int times){ if(times == 0){ ll ret = pow((double)n, 1.0 / p); if(ret == 1) return; ret--; ans += flag * ret; return; } for(int i = start; i < pn; i++){ dfs(i + 1, p * prime[i], times - 1); }}int main(){ get(); while(~scanf("%lld", &n)){ ans = 0; ll ret; flag = -1; for(int i = 1; i <= 3; i++){ flag *= -1; dfs(0, 1, i); } printf("%lld\n", ans + 1); } return 0;}

转载于:https://www.cnblogs.com/KirinSB/p/9555381.html

你可能感兴趣的文章