51Nod 1352 集合计数扩展欧几里得-白红宇的个人博客

51Nod 1352 集合计数扩展欧几里得

发布日期：2021-05-09 04:21:32 浏览次数：15 分类：博客文章

本文共 1358 字，大约阅读时间需要 4 分钟。

基准时间限制：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示例

5 2 4

10 2 3

Output示例

思路：

设A的倍数x，B的倍数y，则有Ax+By=N+1

利用exgcd，求Ax+By=gcd(A,B)的解，在求出符合题意最小的x

要注意x==0的情况是不符合题意的

判断第一组解是否符合题意，不符合

然受剩余的部分除以lcm(A,B)即可得到

注：最后除以lcm的证明

证：当x为最小正整数的第一组解符合题意的时候有（设此时为x0，y0）：

设增量为k,则有：

此时仍要满足以下等式：

对于第一个式子，显然A*x0满足条件，即需要满足：

同理有：

所以k最小为lcm(A,B)

代码：

1 #include 
     
       2 using namespace std; 3 typedef long long ll; 4 ll exgcd(ll a, ll b, ll &x, ll&y) { 5     if(!b) { 6         x=1; 7         y=0; 8         return a; 9     }10     ll ans=exgcd(b,a%b,x,y);11     ll temp=x;12     x=y;13     y=temp-a/b*y;14     return ans;15 }16 int main() {17     ios::sync_with_stdio(false);18     ll T,N,A,B,x,y,sum;19     cin>>T;20     while(T--) {21         sum=0;22         cin>>N>>A>>B;23         ll g=exgcd(A,B,x,y);24         if((N+1)%g!=0) {25             cout<<"0"<
      
       =1&&x*A<=N&&y>=1&&y*B<=N&&((x*A+y*B)==(N+1)))34             sum++;35         else {36             cout<<"0"<
       
        0) sum+=t;44         cout<
        
         <

View Code

上一篇：51nod 1058 N的阶乘的长度位数公式

下一篇：hdu 2669 Romantic 扩展欧几里得

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章