在B*x+9973*y=1的关系；y可以是任何数；
两侧取mod 9973，就得到
B*x mod 9973 =1
#include 'bits/stdc++.h'
using namespace std;
const int md=9973;
typedef long long ll;
ll ex_gcd(ll a,ll b,ll &x,ll &y){
if(b == 0){
x =
1;
y =
0;
return
a;
}
ll r = ex_gcd(b,a%b,y,x);
y -= x*(a/b);
return r;
}//扩展欧几里得模板
int main(){
ll n,B,t,gcd,x,y;
scanf('%lld',&t);
while(t--){
scanf('%lld%lld',&n,&B);
gcd =
ex_gcd(B,md,x,y);
x
=(x*n)%md; //x=A/B,贝祖定理, n =A mod 9973
x = (x+md)
% md;
printf('%lld',x);
}
return 0;
}
解法二：相当于解释了贝祖定理的形成。
本題由题意n=A mod 9973,
改写成n=A-A/9973*9973
因为A/B=X;所以A=n+A/9973*9973=BX;
得到 BX-9973y=n；
因为gcd(B,9973)==1，所以B*X＋9973*y==1存在x,y的整数解，
因此b*x-n一定存在正整数解，并且等于9973*n
由x*B-n=9973y，得到(x*B-n)mod 9973=0，类似《我家的门牌号》
using namespace std;
int main()
{
int t, i, j;
long long n, b, a=9973;
scanf('%d', &t);
while(t--)
{
scanf('%lld%lld', &n, &b);
for(x=0; x
< a; j++)
if((x * b - n) % a == 0) {
//b*x
-n==9973*y;
printf('%d', x);
break;
}
}
return 0;
}
解法三：用费尔马小定理
#include 'bits/stdc++.h'
using namespace std;
const int md=9973;
typedef long long ll;
ll powMod(ll a,ll b)
{
ll ans = 1;
while (b)
{
if
(b&1)
ans = ans * a % md;
a = a*a %
md;
b >>=
1;
}
return ans;
}
int main(){
ll n,B,t,inv,x,y;
scanf('%lld',&t);
while(t--){
scanf('%lld%lld',&n,&B);
inv =
powMod(B,md-2);//表示i的阶乘的逆元
x
=(inv*n)%md; //x=A/B,贝祖定理, n =A mod 9973
x = (x+md)
% md;
printf('%lld',x);
}
return 0;
}
第四个办法，递推法：
递推式如下
inv[i]=(M-M/i)*inv[M%i]%M (其中M为模数，要求为奇质数)
它的推导过程如下：
设t=M/i,k=M%i，那么
t*i+k≡0（Mod
M）
-t*i≡k(Mod M)
对上式两边同时除
i×k，进一步得到
-t*inv[k]≡inv[i](Mod M)
再把和替换掉，最终得到
inv[i]=(M-M/i)*inv[M%i]%M
初始化inv[1]=1，这样就可以通过递推法求出模素数的所有逆元了。
#define N 3000010
typedef long long ll;
using namespace std;
int inv[N],n,p;
int main(){
cin>>n>>p;inv[1]=1;puts('1');
for(int i=2;i<=n;i++){
inv[i]=(ll)(p-p/i)*inv[p%i]%p;//因为inv[p%i]在前一个模板会变成inv[MODc[i]]，会死掉
printf('%d',inv[i]);
}
}
用到这道题上，代码本身说得通，但是由于递推数组有限制，所以，其实用不了；
参考代码：
#include 'bits/stdc++.h'
using namespace std;
const int md=9973;
typedef long long ll;
int inv[1000100],n,p;
int main(){
ll n,B,x,y;
inv[1]=1;
for(int
i=2;i<=1000000;i++)//显然不能满足题目的要求1 < B < 1e9
inv[i]=(md-md/i)*inv[md%i]%md;//因为inv[p%i]在前一个模板会变成inv[MODc[i]]，会死掉
int t;cin>>t;
while(t--){
scanf('%lld%lld',&n,&B);
x
=(n*inv[B])%md; //x=A/B,贝祖定理, n =A mod 9973
x = (x+md)
% md;
printf('%lld',x);
}
return 0;
}
同理换成递归，也是一个样子：B太小时，递归的次数太多，超出了系统栈的限制，程序异常退出
#include 'bits/stdc++.h'
using namespace std;
const int md=9973;
typedef long long ll;
int inv(int b)
{
if(b==1)return 1;
return (md-md/b)*inv(md%b)%md;
}
int main(){
ll n,B,x,y;
int t;cin>>t;
while(t--){
scanf('%lld%lld',&n,&B);
x
=(n*inv(B))%md; //x=A/B,贝祖定理, n =A mod 9973
x = (x+md)
% md;
printf('%lld',x);
}
return 0;
}
二）采用费尔马小定理，直接从阶乘与逆元，获得组合数；
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;//质数
LL fac[1000000+5];//阶乘
LL inv[1000000+5];//逆元
LL powMod(LL a,LL b)
{
LL ans = 1;
while (b)
{
if
(b&1)
ans = ans * a % MOD;
a = a*a %
MOD;
b >>=
1;
}
return ans;
}
void getFac()
{
fac[0] = inv[0] = 1;
for (int i = 1 ; i <= 1000000 ;
i++)
{
fac[i] =
fac[i-1] * i % MOD;
inv[i] =
powMod(fac[i],MOD-2);//表示i的阶乘的逆元
}
}
LL getC(LL n,LL m)
//C(n,m) = n!/((n-m)!*m!) % (1e9+7)
{
return fac[n] * inv[n-m] % MOD * inv[m] %
MOD;
}
int main()
{
getFac();
int n,m;
while (~scanf ('%d
%d',&n,&m))
printf
('%lld',getC((LL)n,(LL)m));
return 0;
}
三）城市建设 P6475
球球是一位建筑师。一天，他收到市长的任务：建设城市。球球打算建造 2n 座高楼。为了保证城市美观，球球做出了如下计划：
球球喜欢整齐的事物。他希望高楼从左向右排成一行，编号依次为 1～2n。
球球喜欢整数，他要求每座高楼的高度都是正整数。
由于材料限制，高楼的高度无法超过 m。
球球喜欢中间高，两边低的造型。他要求前 n 座高楼的高度不下降，后 n 座高楼的高度不上升。
球球打算选两座编号为 x,y 的高楼作为这座城市的地标。他认为只有当这两座高楼高度相等时，才会让城市变得美观。
球球把自己的想法告诉了市长。市长希望得知所有建设城市的方案数。两种方案不同，当且仅当某座高楼的高度在两个方案中不同。这个问题可难倒了球球。球球找到了你，希望你能帮他算出答案。由于答案可能很大，你只需要给出答案对
998244353 取模后的结果。
输入格式
从标准输入读入数据。
仅一行四个整数 m,n,x,y，变量意义见题目描述。
输出格式
输出到标准输出。
仅一行一个整数表示答案。
输入输出样例
输入 #1复制
3 2 1 3
输出 #1复制
10
输入 #2复制
1000 1000 535 1477
输出 #2复制
295916566
说明/提示
对于样例 1，所有的方案为：
{1,1,1,1},{1,2,1,1},{1,3,1,1},{2,2,2,1},{2,2,2,2},{2,3,2,1},{2,3,2,2},{3,3,3,1},{3,3,3,2},{3,3,3,3}。
对于 10% 的数据，1≤n,m≤5。
对于 30% 的数据，1≤n,m≤100。
对于 60% 的数据，1≤n,m≤1000。
对于 100% 的数据，1≤n,m≤10^5
分析：
这是一道组合数学的应用题
情况ABCD分类讨论，
总之最后是求阶乘，由阶乘再要求组合数，数字非常大。
如果不懂逆元的话，用杨辉三角，自求多福；
#define ll long long
#define mod 998244353
using namespace std;
int n,m,x,y;
int t;
int f[5005][5005];
int main(){
scanf('%d%d%d%d',&m,&n,&x,&y);
for(int i=1;i<=n+2;i++){
f[i][1]=1;
for(int
j=2;j<=m+1;j++){
f[i][j]=(f[i-1][j]+f[i][j-1])%mod;
}
}
if(x<=n&&y>n){
int
ans=0;
for(int
i=1;i<=m;i++){
ans=(ans+((ll)f[x][i]*f[n-x+1][m-i+1]%mod*f[y-n][m-i+1]%mod*f[n*2-y+1][i]%mod))%mod;
}
printf('%d',ans);
}
else{
printf('%d',(ll)f[n+1][m]*f[x+n-y+1][m]%mod);
}
return 0;
}
逆元：用前面的模板
using namespace std;
typedef long long LL;
const LL MOD = 998244353;
LL fac[1000000+5];//阶乘
LL inv[1000000+5];//逆元
LL m,n,x,y,ans;
LL quickMod(LL a,LL b)
{
LL ans = 1;
while (b)
{
if
(b&1)
ans = ans * a % MOD;
a = a*a %
MOD;
b >>=
1;
}
return ans;
}
void getFac()
{
fac[0] = inv[0] = 1;
for (int i = 1 ; i <= m+n ; i++)
{
fac[i] =
fac[i-1] * i % MOD;
inv[i] =
quickMod(fac[i],MOD-2);//表示i的阶乘的逆元
}
}
LL getC(LL n,LL m)//C(n,m) = n!/((n-m)!*m!) % (1e9+7)
{
return fac[n] * inv[n-m] % MOD * inv[m] %
MOD;//组合数
}
LL C(LL n,LL m){return getC(m+n-1,n);}//本题组合使用的变形
int main(){
cin>>m>>n>>x>>y;
getFac();
if (x <= n && y > n){
for (int i
= 1;i <= m;i++)
ans = (ans + C(x - 1,i) * C(n - x,m - i +
1) % MOD
* C(y - n -
1,m - i + 1) % MOD * C(n * 2 - y,i) % MOD) % MOD;
}else ans = C(n,m) * C(n + x - y,m) %
MOD;
cout<<ans<<endl;
return 0;
}
