Codeforces 1499D - The Number of Pairs （数学）题意思路代码

89 阅读 0 评论 59 点赞

我是靠谱客的博主大胆外套，这篇文章主要介绍Codeforces 1499D - The Number of Pairs （数学）题意思路代码，现在分享给大家，希望可以做个参考。

Educational Codeforces Round 106 (Rated for Div. 2) D. The Number of Pairs

题意

给定三个正整数 $c, d, x$ ，询问有多少对正整数对 $(a, b)$ ，满足
$c \cdot l c m - d \cdot g c d = x$

限制

$10^4$

$10^7$

思路

对于原式
$c \cdot l c m - d \cdot g c d = x$
由 $g c d$ 及 $l c m$ 的数学性质，很容易得到一个结论： $l c m$ 定是 $g c d$ 的倍数。

那么便能将上式化为
$l c m = x + d ⋅ g c d c lcm=frac{x+dcdot gcd}{c}$
右侧定是一个整数，即 $x + d \cdot g c d$ 定是 $c$ 的倍数

那么我们可以 $O (x)$ 枚举 $x$ 的所有因子作为 $g c d$

由于 $c, d, x$ 已知，在满足上述条件的前提下，可通过 $g c d, c, d, x$ 直接计算出所匹配的 $l c m$

问题现在便转化成了 “在已知 $g c d$ 与 $l c m$ 的前提下求有多少对整数对满足条件”

从数学角度可知

$g c d (a, b)$ 是 $a, b$ 的质因子的交集

$l c m (a, b)$ 是 $a, b$ 的质因子的并集

那么 $l c m g c d frac{lcm}{gcd}$ 便是多出来的质因子的乘积

对于 $l c m g c d frac{lcm}{gcd}$ 的每种质因子，不论数量，都应该全数位于 $a g c d frac{a}{gcd}$ 或者全数位于 $b g c d frac{b}{gcd}$ 中

否则，这些质因子在 $a$ 与 $b$ 中同时出现，便会算在 $g c d$ 中，于此时情况不符

所以如果我们想要构造 $a, b$ 两个数，每种质因子只能够挑其中一个数乘进去

设 $l c m g c d frac{lcm}{gcd}$ 的质因子种类数为 $n$ ，则能够构造出的整数对共有 $2^n$ 种

~~实践可得，~~ 在线的质因子分解算法都将会完美地TLE 15

所以考虑离线处理每个数拥有的质因子种类数

这里的写法类似于埃氏素数筛法，详情见代码部分的 $i n i t$ 函数

注意 $x g c d + d c frac{frac{x}{gcd}+d}{c}$ 的数据范围理论上最大可能达到 $10^7$

代码

(1075ms/2000ms)

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=2e7;
int r[MAXN+50]; //记录每个数字的质因子种类数

void init()
{
    for(int i=2;i<=MAXN;i++)
        if(!r[i]) //判断i是否为素数
        {
            for(int j=i;j<=MAXN;j+=i)
                r[j]++; //i在范围内的倍数的质因子种类数++
        }
}

ll c,d,x,ans;

void add(int gcd)
{
    ll lcm=x+d*gcd;
    if(lcm%c==0)
    {
        lcm/=c;
        if(lcm%gcd==0)
            ans+=1LL<<r[lcm/gcd];
    }
}

void solve()
{
    ans=0;
    cin>>c>>d>>x;
    int s=sqrt(x);
    for(int i=1;i<=s;i++)
    {
        if(x%i==0) //枚举x的因子i
        {
            add(i);
            if(i*i!=x)
                add(x/i);
        }
    }
    cout<<ans<<'n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    init();
    int T;cin>>T;while(T--)
        solve();
    return 0;
}