1352 集合計(jì)數(shù) 基準(zhǔn)時(shí)間限制：1 秒 空間限制：131072 KB 分值: 20 難度：3級算法題 收藏 關(guān)注 給出N個(gè)固定集合{1，N},{2,N-1},{3,N-2},…,{N-1,2},{N,1}.求出有多少個(gè)集合滿足：第一個(gè)元素是A的倍數(shù)且第二個(gè)元素是B的倍數(shù)。 提示： 對于第二組測試數(shù)據(jù)，集合分別是：{1,10},{2,9},{3,8},{4,7},{5,6},{6,5},{7,4},{8,3},{9,2},{10,1}.滿足條件的是第2個(gè)和第8個(gè)。
Input 第1行：1個(gè)整數(shù)T（1<=T<=50000)，表示有多少組測試數(shù)據(jù)。 第2 - T+1行：每行三個(gè)整數(shù)N，A,B（1<=N，A，B<=2147483647) Output 對于每組測試數(shù)據(jù)輸出一個(gè)數(shù)表示滿足條件的集合的數(shù)量，占一行。 Input示例 2 5 2 4 10 2 3 Output示例 1 2
題解：用擴(kuò)展歐幾里得的公式求解的個(gè)數(shù)，首先要求出一個(gè)最小解，然后找到a和b 的最小公倍數(shù)，然后一個(gè)莫名其妙的原理就可以解出來了
#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) {新聞熱點(diǎn)
疑難解答
