GCD and LCM HDU - 4497

题目链接:https://vjudge.net/problem/HDU-4497

题意:求有多少组(x,y,z)满足gcd(x,y,z)=a,lcm(x,y,z)=b。

思路:对于x,y,z都可以写成x = p1^a1+p2^a2+p3^a3....pn^an;y = p1^b1+p2^b2+p3^b3....pn^bn;z=p1^c1+p2^c2+p3^c3....pn^cn;
          x,y,z的最大公约数可以写成gcd(x,y,z) = p1^min(a1,b1,c1)*p2^min(a2,b2,c2)......pn^min(an,bn,cn);
          最小公倍数则是lcm(x,y,z) = p1^max(a1,b1,c1)*p2^max(a2,b2,c2)....*pn^max(an,bn,cn)
          对于gcd(x,y,z) = g,lcm(x,y,z) = l的组合数等gcd(x,y,z) = 1,lcm(x,y,z) = l/g;
          设l/g = k;
          k = p1^d1+p2^d2+.....+pn^dn;
          这样对于p1来说a1,b1,c1中一定有一个为0,因为gcd(x,y,z) = 1,同理也一定有一个为d1;
         分为三种情况分别是2个0一个d1,2个d1一个0,1个d1一个0另外一个是[1,(d1-1)]中的一个数,则情况数便是3+3+(d1-1)*6 = 6*d1;
         最终答案便是

         ans = 1;
         for(int i=1;i<=n;i++)
             ans*=di*6;

GCD and LCM HDU - 4497
  1 #include<time.h>
  2 #include <set>
  3 #include <map>
  4 #include <stack>
  5 #include <cmath>
  6 #include <queue>
  7 #include <cstdio>
  8 #include <string>
  9 #include <vector>
 10 #include <cstring>
 11 #include <utility>
 12 #include <cstring>
 13 #include <iostream>
 14 #include <algorithm>
 15 #include <list>
 16 using namespace std;
 17 #define eps 1e-10
 18 #define PI acos(-1.0)
 19 #define lowbit(x) ((x)&(-x))
 20 #define zero(x) (((x)>0?(x):-(x))<eps)
 21 #define mem(s,n) memset(s,n,sizeof s);
 22 #define ios {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
 23 typedef long long ll;
 24 typedef unsigned long long ull;
 25 const int maxn=1e5+5;
 26 const int Inf=0x7f7f7f7f;
 27 const ll Mod=999911659;
 28 //const int N=3e3+5;
 29 bool isPowerOfTwo(int n) { return n > 0 && (n & (n - 1)) == 0; }//判断一个数是不是 2 的正整数次幂
 30 int modPowerOfTwo(int x, int mod) { return x & (mod - 1); }//对 2 的非负整数次幂取模
 31 int getBit(int a, int b) { return (a >> b) & 1; }// 获取 a 的第 b 位,最低位编号为 0
 32 int Max(int a, int b) { return b & ((a - b) >> 31) | a & (~(a - b) >> 31); }// 如果 a>=b,(a-b)>>31 为 0,否则为 -1
 33 int Min(int a, int b) { return a & ((a - b) >> 31) | b & (~(a - b) >> 31); }
 34 ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
 35 ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
 36 int Abs(int n) {
 37   return (n ^ (n >> 31)) - (n >> 31);
 38   /* n>>31 取得 n 的符号,若 n 为正数,n>>31 等于 0,若 n 为负数,n>>31 等于 -1
 39      若 n 为正数 n^0=n, 数不变,若 n 为负数有 n^(-1)
 40      需要计算 n 和 -1 的补码,然后进行异或运算,
 41      结果 n 变号并且为 n 的绝对值减 1,再减去 -1 就是绝对值 */
 42 }
 43 ll binpow(ll a, ll b,ll c) {
 44   ll res = 1;
 45   while (b > 0) {
 46     if (b & 1) res = res * a%c;
 47     a = a * a%c;
 48     b >>= 1;
 49   }
 50   return res%c;
 51 }
 52 void extend_gcd(ll a,ll b,ll &x,ll &y)
 53 {
 54     if(b==0) {
 55         x=1,y=0;
 56         return;
 57     }
 58     extend_gcd(b,a%b,x,y);
 59     ll tmp=x;
 60     x=y;
 61     y=tmp-(a/b)*y;
 62 }
 63 ll mod_inverse(ll a,ll m)
 64 {
 65     ll x,y;
 66     extend_gcd(a,m,x,y);
 67     return (m+x%m)%m;
 68 }
 69 ll eulor(ll x)
 70 {
 71    ll cnt=x;
 72    ll ma=sqrt(x);
 73    for(int i=2;i<=ma;i++)
 74    {
 75     if(x%i==0) cnt=cnt/i*(i-1);
 76     while(x%i==0) x/=i;
 77    }
 78    if(x>1) cnt=cnt/x*(x-1);
 79    return cnt;
 80 }
 81 ll p[maxn],cnt;
 82 ll a,b,n;
 83 ll num[maxn];
 84 void getp(ll x)
 85 {
 86     cnt=0;
 87     p[cnt++]=x;
 88     for(ll i=2;i*i<=x;i++)
 89     {
 90         if(x%i==0)
 91         {
 92             p[cnt++]=i;
 93             if(i!=x/i)
 94             {
 95                 p[cnt++]=x/i;
 96             }
 97         }
 98     }
 99     sort(p,p+cnt);
100     return;
101 }
102 ll ans[maxn];
103 int main()
104 {
105     int t;
106     scanf("%d",&t);
107     while(t--)
108     {   
109         mem(ans,0);
110         ll a,b;
111         scanf("%lld%lld",&a,&b);
112         if(b%a)
113         {
114             puts("0");
115             continue;
116         }
117         ll sum=1;
118         ll c=b/a;
119         int cnt=0;
120         for(int i=2;i<=c;i++)
121         {
122             if(c==0) break;
123             if(c%i==0)
124             {
125                 while(c%i==0)
126                 {
127                     ans[cnt]++;
128                     c/=i;
129                 }
130                 cnt++;
131             }
132         }
133         for(int i=0;i<cnt;i++)
134         {
135             if(ans[i])
136             { 
137                 //cout<<ans[i]<<endl;
138                 sum*=ans[i]*6;
139             }
140         }
141         cout<<sum<<endl;
142     }
143     return 0;
144 }
View Code

 

上一篇:记录第一篇博客codeforces round #641 div2


下一篇:Pairs Forming LCM LightOJ - 1236