1352 集合計數 基準時間限制：1 秒 空間限制：131072 KB 分值: 20 難度：3級算法題 收藏 關注 給出N個固定集合{1，N},{2,N-1},{3,N-2},…,{N-1,2},{N,1}.求出有多少個集合滿足：第一個元素是A的倍數且第二個元素是B的倍數。 提示： 對于第二組測試數據，集合分別是：{1,10},{2,9},{3,8},{4,7},{5,6},{6,5},{7,4},{8,3},{9,2},{10,1}.滿足條件的是第2個和第8個。
Input 第1行：1個整數T（1<=T<=50000)，表示有多少組測試數據。 第2 - T+1行：每行三個整數N，A,B（1<=N，A，B<=2147483647) Output 對于每組測試數據輸出一個數表示滿足條件的集合的數量，占一行。 Input示例 2 5 2 4 10 2 3 Output示例 1 2
題解：用擴展歐幾里得的公式求解的個數，首先要求出一個最小解，然后找到a和b 的最小公倍數，然后一個莫名其妙的原理就可以解出來了
#include <cstdio>#include <cstring>#include <math.h>#include <algorithm>using namespace std;#define LL long long#define MOD 1000000007#define M 200010#define INF 0x3f3f3f3fLL n;LL exgcd(LL a, LL b, LL &d, LL &x, LL &y){ if(!b) { d = a; x = 1; y = 0; } else { exgcd(b, a%b, d, y, x); y -= x * (a / b); }}int main(){ int t; LL x, y, k, d, a, b, bl, xm, ym, al, num; scanf("%d", &t); while(t--) { scanf("%lld%lld%lld", &n, &a, &b); exgcd(a, b, d, x, y); n++; k = n / d; if(n % d != 0) {新聞熱點
疑難解答
