Educational Codeforces Round 106 (Rated for Div. 2)Educational Codeforces Round 106 (Rated for Div. 2)

124 阅读 0 评论 82 点赞

我是靠谱客的博主壮观绿草，这篇文章主要介绍Educational Codeforces Round 106 (Rated for Div. 2)Educational Codeforces Round 106 (Rated for Div. 2)，现在分享给大家，希望可以做个参考。

Educational Codeforces Round 106 (Rated for Div. 2)

D. The Number of Pairs

题意：

给定 $c, d, x$ ，让你求有多少对 $a, b$ 可以让， $c * l c m (a, b) - d * g c d (a, b) = x$

题解：

设 $t = l c m (a, b), g = g c d (a, b)$

可以得到 $c * t - d * g = x$

因为 $g ∣ t$

所有方程有解时， $g ∣ x$

所有将方程除上 $g$ , 即： $c ∗ t g − d = x g c * frac{t}{g} - d = frac{x}{g}$

$g ∣ x$ ， $g$ 为 $x$ 的因子

枚举 $x$ 所有因子可以求出 $x g frac{x}{g}$ 的值，设 $y = x g y = frac{x}{g}$

将上述方程进行整理： $t g = y + d c frac{t}{g} = frac{y + d}{c}$

右边的都是已知量。

左边：因为 $a * b = l c m (a, b) * g c d (a, b)$ ，所有 $t = l c m ( a , b ) = a ∗ b g c d ( a , b ) t = lcm(a, b) = frac{a * b}{gcd(a, b)}$

所以 $^2} = frac{a}{g} * frac{b}{g}$

所以 $a g ∗ b g = y + d c frac{a}{g} * frac{b}{g} = frac{y + d}{c}$

因为 $g = g c d (a, b)$

所以 $g c d ( a g , b g ) = 1 gcd(frac{a}{g}, frac{b}{g}) = 1$

也就是说 $y + d c frac{y + d}{c}$ 中有多少对因子 $f, z$ ，使得 $f ∗ z = y + d c f * z = frac{y +d}{c}$ 且 $g c d (f, z) = 1$

可以将 $y + d c frac{y + d}{c}$ 的所有质因子求出来，那么上述条件的方案数就是，对于每种质因子， 要么全部都要

要么都不要，也就是说 $(f, z)$ 有 $2 ^ n$ 种方案（ $n$ 是 $y + d c frac{y +d}{c}$ 的质因数种类）。那么等价于 $(a, b)$ 有 $2 ^ n$ 中方案。

所以时间复杂度为 $q * s q r t (n)$

代码：

复制代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e7 + 7;
int vis[N], cnt[N];
ll c, d, x;
ll work(ll g) {
if ((x / g + d) % c) return 0;
return 1ll* 1 << 1ll*cnt[(x / g + d) / c];
}
int main() {
for (int i = 2; i < N; i++) {
if (vis[i]) continue;
for (int j = i; j < N; j += i) {
cnt[j]++;
vis[j] = 1;
}
}
int t; scanf("%d", &t);
while (t--) {
scanf("%lld %lld %lld", &c, &d, &x);
ll ans = 0;
for (ll i = 1; i * i <= x; i++) {
if (x % i == 0) {
ans += work(i);
if (x / i != i) ans += work(x / i);
}
}
printf("%lldn", ans);
}
}