【组合数学+exgcd】集合计数

我会带着你远行 2024-03-22 12:43 41阅读 0赞

**思路大概差不多，就是求exgcd**

**但是不知道怎么求解的个数，这道题其实就是在问解的个数**

[问题-集合计数 (51nod.com)][-_ _51nod.com]

题意：

![d3982b79f96048c6a4337cdd1f5d3e51.png][]

思路：

![b0217179856948e3887fb96571a3d92b.jpeg][]

假设我们求的最小的k1

那么每次让k2退lcm(a,b)格就是一个解

所以解的个数就是res/lcm(a,b)

注意求k1最小正整数解的时候应该注意：

![7ebc52a871fc447e8e3efe6e0e0a4bca.png][]

Code：

#include <bits/stdc++.h>
    
    #define int long long 
    
    using namespace std;
    
    const int mxn=2e6+10; 
    const int mod=1e9+7;
    
    int N,A,B,x,y;
    
    int exgcd(int a,int b,int &x,int &y){
        if(!b){
            x=1,y=0;
            return a;
        }
        int d=exgcd(b,a%b,y,x);
        y-=(a/b)*x;
        return d;
    }
    int lcm(int a,int b){
    	return a*b/__gcd(a,b);
    }
    void solve(){
    	cin>>N>>A>>B;
    	int D=exgcd(A,B,x,y);
    	if((N+1)%D!=0) cout<<0<<'\n';
    	else{
    		x=x*(N+1)/D;
    		int r=B/D;
    		x=(x%r+r)%r;
    		if(x==0) x+=r;
    		int res=(N)-x*A;
    		if(res<0) cout<<0<<'\n';
    		else cout<<res/lcm(A,B)+1<<'\n';
    	}
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	while(__--)solve();return 0; 
    }

[-_ _51nod.com]: http://www.51nod.com/Question/Index.html#questionId=1286
[d3982b79f96048c6a4337cdd1f5d3e51.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/2ed5677fe9724b19894c98e17dbc409a.png
[b0217179856948e3887fb96571a3d92b.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/f22b1a0accf04f49b1823f90f40357ba.png
[7ebc52a871fc447e8e3efe6e0e0a4bca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b037be409f0f4473a23f2061830c5877.png

发表评论取消回复

表情：

评论列表（有 0 条评论，41人围观）

还没有评论，来说两句吧...

相关阅读

相关【组合计数】CF1151E

[Problem - 1151E - Codeforces][] 题意： ![9af8880daced4f3d9b418de0063025f6.png][] ![bb2f

迈不过友情╰/ 2024年03月22日 23:59/ 0 赞/ 73 阅读

相关【组合数学+exgcd】集合计数

思路大概差不多，就是求exgcd 但是不知道怎么求解的个数，这道题其实就是在问解的个数 [问题-集合计数 (51nod.com)][-_ _51nod.com] 题意：

我会带着你远行/ 2024年03月22日 12:43/ 0 赞/ 42 阅读

相关【组合计数】CF1866 H

[Problem - H - Codeforces][] 题意 ![ae0ad641c2c842abbdd97f19e7c95ea2.png][] 思路不知道这种tr

末蓝、/ 2024年02月20日 09:05/ 0 赞/ 51 阅读

相关数字组合（背包计数）

2046: 数字组合时间限制: 0 Sec 内存限制: 128 MB 提交: 2 解决: 1 \[ [提交][Link 1]\]\[ [状态][Link 2]\

柔情只为你懂/ 2024年02月18日 14:36/ 0 赞/ 53 阅读

相关组合数学-抽屉原理

文章目录抽屉原理例题 HDU-1205 POJ-2356 抽屉原理 -------------------- 抽屉原理

迷南。/ 2022年11月28日 13:19/ 0 赞/ 310 阅读

相关【离散数学】计数原理

这里介绍三个基本计数原理：鸽巢原理、加法原理、乘法原理。鸽巢原理：假设要把一些鸽子放到鸽笼中去，鸽子的总数多于鸽笼总数，那么一定有某个鸽笼里至少有两只鸽子。更一般地，如果鸽

小咪咪/ 2022年11月06日 14:52/ 0 赞/ 232 阅读

相关 Stirling数-组合数学

Stirling数一、定义 Stirling数可以指两类数，第一类数是有正负的，其绝对值是包含n个元素的集合分作k个环排列的方法数目；第二类

Myth丶恋晨/ 2022年08月21日 06:54/ 0 赞/ 195 阅读

相关组合数学选择题

1.【题目】美团有个传统，就是公司各部门每月都要组织员工进行一次团建互动(team building，简称TB)，每个员工都可以带家属参加。活动内容出了吃喝玩之外，还要做一些互

梦里梦外;/ 2022年05月18日 08:27/ 0 赞/ 296 阅读

相关组合数学 (二): 排列组合

排列组合公式排列组合代码输出所有排列错位排列输出所有组合公式排列从

本是古典何须时尚/ 2022年02月21日 14:54/ 0 赞/ 346 阅读

相关组合数学 (三): 排列组合的数学逻辑

排列组合的数学逻辑前言排列圆排列项链排列组合 n 个相同的小球放到 m 个相同的盒子里

怼烎@/ 2022年02月14日 01:18/ 0 赞/ 664 阅读