费马小定理【模板例题】

蔚落 2022-12-10 15:56 198阅读 0赞

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

--------------------

#### 例题 ####

First：[牛牛和牛可乐的赌约][Link 2]  
![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]

##### 题目原理 #####

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

##### 变式可得 #####

**(1/n)%mod ==> nmod-1/ n ==> nmod-2**

[推荐快速幂博客][Link 3]  
（由于 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：[抽卡][Link 4]  
![题目1][1]  
![题目2][2]  
![题目3][3]

#### 解题思路 ####

①、抽到牌概率 = 总概率 - 抽不到牌概率  
②、费马小定理变形：(1/n)%mod = nmod-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;
    }

[Link 1]: https://blog.csdn.net/qq_39435411/article/details/106067717
[Link 2]: https://ac.nowcoder.com/acm/contest/7412/A
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/3b86e7585245443380f427bd8d22e4af.png
[Link 3]: https://blog.csdn.net/qq_19782019/article/details/85621386?utm_source=distribute.pc_relevant.none-task
[Link 4]: https://ac.nowcoder.com/acm/contest/5600/D
[1]: /images/20221123/2c5f454738d74296bc669c303b232a63.png
[2]: /images/20221123/7f5c35c1d8574019acd9e2e862f3979e.png
[3]: /images/20221123/0e50fb7fffa0437e9ddb57f582ca51f5.png