The 2021 ICPC Asia Taipei Regional Programming Contest L. Leadfoot（组合数学/2-adic赋值函数+kummer定理）

这个题意还是看题面比较好

司机个数未知，每个司机初始赢0局，输0局，

两个当前赢的局数和输的局数相同的司机，会在一起比赛一局，

比完之后，其中一个司机赢的局数+1，另一个司机输的局数+1，

司机当他总共赢了n场，或总共输了m场之后就不再继续比赛，

你想邀请最少的司机数，使得每个人都能要么总共赢n场，要么总共输m场，

其中，赢了0场、输了m场的司机将会被授予Leadfoot badges，

k(k<=1e5)组样例，每次给出n,m(1<=n,m<=1e5)，

每次询问最少需要准备多少个Leadfoot badges，答案对1e9+7取模

思路来源

官方题解

实际上，司机人数够用，等价于比赛的任意一个步骤的人数都是整数，

题解中提到了2-adic valuation/kummer lemma，听上去比较高端，实际上，

2-adic valuation，2-进赋值函数，可以被认为是一个数包含多少个2的幂次，

假设最后一局是赢，则前面一定是赢了n-1局，且输了j场(0<=j

假设最后一句是输，同理，前面输了m-1局，赢了i场(0<=i

假设司机人数是64（包含7个2的幂次），而某个终态C(n-1+j,j)的值包含3个2的幂次（不妨是8），

则此时，司机人数是8，终态C(n-1+j,j)的值是1，是该种终态对应的最优司机人数，

依次根据每个终态，求出对应的最优司机人数，最大的那个即为司机实际最少人数

求出最少司机个数后，除以2的m次方，即是连输m场的人的最少个数

实际上，根据kummer定理，

C(n+m,m)在二进制下包含2的幂次，等于m+n在二进制下加法的进位次数，

2e5的二进制位不足20，进位次数不会超过20，即包含2的幂次不会超过20，

所以，只检查[max(0,i-20),i]和[max(0,j-20),j]即可

#include
using namespace std;
const int N=2e5+10,mod=1e9+7;
#define dbg(x) cerr<<#x<<":"<<(x)<