D. The Number of Pairs

2024-04-27 12:18

文章标签 number pairs

本文主要是介绍D. The Number of Pairs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

(我发现这样的题目都是分解因子)

我们设a = Ag, b = Bg, lcm = (Ag * Bg) / g = AB * g, 此时方程可化为g(c * AB - d) = x。由此我们可以知道,g一定为x的一个因子, 那么(cAB - d)就是另外一个因子。当我们求得一个因子i，令g = i, 则 AB * c = x/i + d, 当x/i + d能被c整除时，我们可以得到AB的值。因为gcd(A,B) == 1,所以当我们找出AB的素因子后，该因子一定只能是A,B其中一个的因子,所有我们可以找出AB的所有素因子将他们分配给A和B,一共就有2^cnt种情况( C(n,0) + C(n, 1) …)
a = Ag, b = B*g, 故a, b的组合数就等于A, B的组合数.

算法实现

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<utility>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cctype>
using namespace std;typedef long long LL;           //数据太大了记得用LL,还有把INF也得换
typedef pair<int, int> P;const int maxn = 2e7+10;        //cf数组最多差不多是这么多，1e8就会段错误
const int V_MAX = 800 + 10;
const int mod = 10007;
const int INF = 0x3f3f3f3f;     //如果数据范围为long long，记得把INF的值换了
const double eps = 1e-6;        //eps开太小二分容易死循环,所以直接来个100次循环就好了//多组输入时,maxn太大,用memset()会超时,血的教训;int mind[maxn], val[maxn];void solve() {int c, d, x;cin >> c >> d >> x;int res = 0;for(int i = 1; i*i <= x; i++) {if(x % i != 0) continue;int k1 = x/i + d;if(k1 % c == 0) res += 1 << val[k1 / c];if(i * i == x) continue;int k2 = i + d;if(k2 % c == 0) res += 1 << val[k2 / c];}cout << res << endl;
}int main()
{ios::sync_with_stdio(false);           //关了流同步就别用c的输入//freopen("D:\\in.txt", "r", stdin);//先求出每个数的素因子个数.memset(mind, -1,sizeof mind);mind[1] = 1;for(int i = 2; i <= maxn; i++) {if(mind[i] == -1) {for(int j = i; j <= maxn; j += i) {mind[j] = i;}}}for(int i = 2; i <= maxn; i++) {int t = i / mind[i];val[i] = val[t] + (mind[i] != mind[t]);}int t; cin >> t;while(t--) {solve();}return 0;
}