POJ 2773 Happy 2006 （容斥原理）-白红宇

POJ 2773 Happy 2006 （容斥原理）

阅读量：6537 次

发布时间：2019-06-24

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

　　题目是给出m，k。找到跟第k个跟m互素的数是多少。

　　构造肯定不行，再加上数据范围，只能二分。思路是二分枚举[1,2^64]范围内所有的数x，找到1到x范围内与m不互素的数的个数y（用容斥原理）。然后用x - y，如果等于k就是结果。

找到1到x范围内与m不互素的数的个数y：这个过程可以先把m分解质因子，记录m所有的质因子。f[i]表示含有i个质因子的数的个数。ans = m - f(1) + f(2) - f(3) ....

ps:这里二分要找满足 == k最左边的数，推了半天发现把二分写错了。。。T_T

//#pragma comment(linker,"/STACK:327680000,327680000")#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #define CL(arr, val) memset(arr, val, sizeof(arr))#define REP(i, n) for((i) = 0; (i) < (n); ++(i))#define FOR(i, l, h) for((i) = (l); (i) <= (h); ++(i))#define FORD(i, h, l) for((i) = (h); (i) >= (l); --(i))#define L(x) (x) << 1#define R(x) (x) << 1 | 1#define MID(l, r) (l + r) >> 1#define Min(x, y) (x) < (y) ? (x) : (y)#define Max(x, y) (x) < (y) ? (y) : (x)#define E(x) (1 << (x))#define iabs(x) (x) < 0 ? -(x) : (x)#define OUT(x) printf("%I64d\n", x)#define Read() freopen("data.in", "r", stdin)#define Write() freopen("data.out", "w", stdout);typedef long long LL;const double eps = 1e-8;const double pi = acos(-1.0);const double inf = ~0u>>2;using namespace std;const int N = 1000010;int p[N], cnt;void init(int m) { cnt = 0; for(int i = 2; i*i <= m; ++i) { if(m%i == 0) { p[cnt++] = i; while(m%i == 0) {m /= i;} } } if(m != 1) p[cnt++] = m;}LL cal(LL n) { int i, j, bit; LL res = 0, sum; for(i = 1; i < 1<
                   
                    > m >> k, !cin.eof()) { init(m); LL l = 1, r = (1LL<<60), mid, tmp; while(r - l > 0) { mid = MID(l, r); tmp = cal(mid); if(tmp >= k) r = mid; else l = mid + 1; } printf("%lld\n", l); } return 0;}

转载地址：http://bjbdo.baihongyu.com/

你可能感兴趣的文章