费马小定理【模板例题】

费马小定理：
如果p是一个质数，而整数a不是p的倍数，
则有a^（p-1）≡1（mod p）。
即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1
变式延伸：
在对质数 p 求余的条件下
n * a^p-1 ≡ n * 1 = n
a^p-2 ≡ a^-1 * 1 = a^-1　　
a^b ≡ a ^b-p+1　
(≡：等价）
费马小定理参考博客

例题

First：牛牛和牛可乐的赌约

题目原理

ans = mod + 1 - ( (1/n) % mod)^m

变式可得

(1/n)%mod ==> n^mod-1/ n ==> n^mod-2

推荐快速幂博客
（由于 mod 与 m 都很大，再利用快速幂即可得到答案）

#include<stdio.h>
#define ll long long
const ll mod = 1e9+7;

ll quick(ll base, ll power)	//快速幂
{
	long long result=1;
	while(power)
	{
		if(power&1)//只有奇数才乘以底数
			result=result*base%mod;
		base=base*base%mod;
		power=power>>1;
	}
	if(base==0){
		result=0;
	}
	return result%mod;
}

int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		ll n, m, ans;
		scanf("%lld%lld", &n, &m);
		ans = quick(n, mod-2)%mod;
		ans = quick(ans, m);
		ans = mod+1-ans;
		printf("%lld", ans);
		if(t!=0) printf("\n");
	}
	
	return 0;
}

Second：抽卡

解题思路

①、抽到牌概率 = 总概率 - 抽不到牌概率
②、费马小定理变形：(1/n)%mod = n^mod-1

实现代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100010]={0}, b[100010]={0};
const int mod = 1e9+7;

ll quick(ll base, ll power){
	ll ans=1;
	while(power){
		if(power&1)
			ans = ans*base%mod;
		power >>= 1;
		base = base*base%mod;
	}
	if(base==0) 
		return 0;
	return ans;
}

int main(){
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++) scanf("%d", &a[i]);
	for(int i=0; i<n; i++) scanf("%d", &b[i]);
	
	ll ans=1;
	for(int i=0; i<n; i++){
		ans = (ans*(a[i]-b[i])%mod)*quick(a[i], mod-2)%mod;
	}
	
	printf("%d", (mod-ans+1)%mod);
	
	return 0;
}