标签归档:LCM

NOIP2009 -HanKSon的趣味题


题意:
有n个询问,在每个询问中,先给定四个自然数a,b,c,d,然后求出有多少个x满足\( gcd(a,x)=b\) 并且\(lcm(c,x)=d\). 数据范围:\(n<=2000,1<=a,b,c,d<=2*10^9\).

Solution:
这道题有多种办法:题解

一开始尝试暴力解法,枚举d的约数,然后直接判断是否符合题目的两个条件,最后一组数据果然超时了.然后书上还有通过质因子构造约数的方法,还未尝试过.在网上看题解时发现暴力解法还可以优化,主要是要想到下面这条性质来加速GCD运算:
对两个正整数\(a,b\),设 \(gcd(a,b)=k\),则有 \(gcd(a/k,b/k)=1\).

明天写一下其他思路. 还是太菜了啊,抓紧学习啊!

暴力优化法:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;
#define MAX_N 2e9

typedef long long ll;
typedef unsigned long long ull;

int gcd(int a, int b) {
  if (b) return gcd(b, a % b);
  return a;
}

int main() {
  int n;
  cin >> n;
  while (n--) {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    int ans = 0;
    for (int i = 1; i*i <= d; i++) {
      if(d%i==0){
          if (i%b==0&&gcd(a/b, i/b) == 1&& gcd(d/i,d/c)==1) {
             ans++;
          }
          int j=d/i;
          if(j!=i){
              if(j%b==0&&gcd(a/b,j/b)==1&& gcd(d/j,d/c)==1){
                  ans++;
              }
          }
      }
    }
    cout<<ans<<endl;
  }

  return 0;
}