首页 > 代码库 > 51nod 1352 集合计数(扩展欧几里得)
51nod 1352 集合计数(扩展欧几里得)
题目链接:传送门
题意:略
分析:
非常easy能够得到一个方程 A*x + B*y = N + 1
这式子能够用扩展GCD求出gcd,x和y,然后我们求出大于0的最小x,A*x第一个满足条件的集合firstSet,剩下的N-firstSet个集合能够直接除LCM(A,B)(A和B的最小公倍数)统计出数量。
代码例如以下:
#include <stdio.h> #include <string.h> #include <iostream> #define LL long long using namespace std; LL exgcd(LL a, LL b, LL &x, LL &y) { LL r,t; if(b==0) { x=1; y=0; return a; } r=exgcd(b,a%b,x,y); t=x; x=y; y=t-a/b*y; return r; } int main() { int t; scanf("%d", &t); while(t--) { LL ans = 0; LL N, A, B; LL xx,yy,d,r; scanf("%I64d%I64d%I64d",&N, &A, &B); d=exgcd(A, B, xx, yy); if(((N + 1) % B) % d != 0) ans = 0; else { LL lcm = A * B / d; xx = xx *(((N + 1) % B) / d); r = B / d; xx=(xx % r + r) % r; if(xx == 0) { xx = lcm / A; } if(xx * A > N) { ans = 0; printf("%I64d\n", ans); continue; } ans += ((N - xx * A) / lcm); ans++; } printf("%I64d\n", ans); } return 0; }
51nod 1352 集合计数(扩展欧几里得)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。