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\ast lcm(a,b)-d\ast gcd(a,b)=x$

题解：

设$t=lcm(a,b),g=gcd(a,b)$

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

因为$g|t$

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

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

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

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

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

右边的都是已知量。

左边：因为 $a\ast b=lcm(a,b)\ast gcd(a,b)$ ， 所有$t=lcm(a,b)=\frac{a\ast b}{gcd(a,b)}$

所以$\frac{t}{g}=\frac{a\ast b}{gcd(a,b)\ast gcd(a,b)}=\frac{a\ast b}{g^2}=\frac{a}{g}\ast \frac{b}{g}$

所以$\frac{a}{g}\ast \frac{b}{g}=\frac{y+d}{c}$

因为 $g=gcd(a,b)$

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

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

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

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

所以时间复杂度为$q\ast sqrt(n)$

代码：

#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);
}
}

最后

以上就是壮观绿草为你收集整理的Educational Codeforces Round 106 (Rated for Div. 2)Educational Codeforces Round 106 (Rated for Div. 2)的全部内容，希望文章能够帮你解决Educational Codeforces Round 106 (Rated for Div. 2)Educational Codeforces Round 106 (Rated for Div. 2)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。