題目鏈接

題目大意

給定正整數 $b,d$，求存在多少組正整數 $a,b$ ，滿足 $\frac{a}{b}+\frac{c}{d}=\frac{b}{d}$

解題思路

式子變形得 $a=\frac{b(b?c)}{d}$ ,那么就是找有多少個可以正整數 $c$ 的值，能讓 $a$ 也為正整數。
顯然，$c$ 的取值范圍為 $(0,b)$ 之內的正整數。那么那些可以讓右側分式可以整除呢？我們可以先將 $b$ 和 $d$ 約分，得到 $a=\frac{p(b?c)}{q}$ ，其中 $p,q$ 互質。然后只有 $b?c$ 是 $q$ 的倍數時，才能讓 $a$ 是正整數

參考代碼

#include<bits/stdc++.h> using namespace std; int main(){int n;cin >> n;while(n --){int b, d;cin >> b >> d;d /= __gcd(b, d);cout << (b + d - 1) / d - 1 << '\n';}return 0; }

注：如果想要求 $?\frac{a}{b}?$，可以計算 $(a+b?1)/b$

總結

以上是生活随笔為你收集整理的Codeforces::GYM 102896E Easy Measurements的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。