HDU 1695 GCD★(反発原理＋オラ関数)

2785 ワード

HDU

テーマリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=1695
タイトル:[1.b]のxと[1.d]のyはどれぐらいgcd(x,y)=kがありますか?
構想:予備知識:
反発原理は、数区間[1.r]のnとの間の相互の数の個数を求めます.
ヘレはgcd(x,y)=kを要求すると、gcd(x/k,y/k)=1を求める問題になります.だから、問題は[1.b/k]と[1.d/k]の中にどれぐらいのペアがあるかを求めます.また、この問題はgcd(1,3)とgcd(3)を求めます.容斥原理で解決します.[x.d/k]=[1.d/k]-[1.x-1],[1.d/k]上の容斥原理で解決できます.[1.x-1]も収容できますが、速度が遅く、明らかにより速いリラ関数で行うことができます.


#include 
 
   
    
  
#include 
  
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
            #include 
            
              #include 
             
               #include 
              
                #define MID(x,y) ((x+y)>>1) using namespace std; typedef long long LL; //max long long == 9223372036854775807LL LL phi(LL n) { if (n == 1) return 0; LL i,sum=n; for(i=2; i*i<=n; i++) { if(n%i==0) { sum = sum / i * (i-1); do { n/=i; } while(n%i==0); } } if(n>1) sum = sum / n * (n - 1); return sum; } int solve(int r, int n){ if (r == 0) return 0; int res = 0; vector 
               
                 p; for (int i = 2; i * i <= n; i ++){ if (n % i == 0){ p.push_back(i); while(n % i == 0){ n /= i; } } if (n == 1) break; } if (n > 1) p.push_back(n); for (int msk = 1; msk < (1 << p.size()); msk ++){ int mult = 1, bit = 0; for (int i = 0; i < p.size(); i ++){ if (msk & (1 << i)){ bit ++; mult *= p[i]; } } int cur = r / mult; if (bit % 2 == 1){ res += cur; } else{ res -= cur; } } return r - res; } int main(){ int t, caseo = 1; cin>>t; while(t --){ int a,b,c,d,k; cin>>a>>b>>c>>d>>k; if (k == 0){ cout<<"Case "< 
                
                  d){ int tmp = d; d = b; b = tmp; } LL ans = 0; for (int i = 1; i <= b; i ++){ ans += (LL)solve(d, i) - phi(i); } cout<<"Case "<

iniファイル操作関連