ICPC网络赛2A&&费马小定理

题目链接:

https://pintia.cn/problem-sets/1574060137151397888/exam/problems/1574060247893606400

费马小定理：如果p是一个质数，而整数a不是p的倍数(gcd(p,a)=1)，则有a^（p-1）≡1（mod p）。

证明：费马小定理_百度百科 (baidu.com) 大概就是构造一个剩余系通过分析消去后得到

应用：计算指数对一个素数的模

A题题解：

对n小于等于100可以直接暴力计算最后一行（即各位）的模、

n大于100时候：题目给出的质数p的范围与10的最大公约数为1

a^（p-1）≡1（mod p）每过p-1位10^(p-1)就会出现循环，所以只要找前mod-1项10^((n-i)%(mod-1))与和相乘(模的加减乘定理)累加取模

计算第(模-1)行即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t,n,q,ask;
 4 int s[101][101];
 5 int g[101],p[101];
 6 /*因为1e6不会到所以不用那么大到10的n-1次方*/
 7 void init(){
 8     for(int i=1;i<=100;i++){
 9         g[i]=(n-i)%(ask-1);
10         p[i]=1;
11     }
12     for(int i=1;i<=100;i++){
13         for(int j=1;j<=g[i];j++){
14             p[i]=(p[i]*10)%(ask);
15         }
16     }
17     
18 }
19 int main(){
20     cin>>t;
21     while(t--){
22         cin>>n;
23         for(int i=1;i<=min(n,100);i++){
24             for(int j=1;j<=i;j++){
25                 cin>>s[i][j];
26             }
27         }
28         cin>>q;
29         while(q--){
30             
31             cin>>ask;
32             if(ask<=100){
33                 int ans=0;
34                 for(int i=1;i<=min(n,100);i++){
35                     ans=(ans*10+s[n][i])%ask;
36                 }
37                 cout<<ans<<"\n";
38             }else{
39                 int ans=0;
40                 init();
41                 for(int i=1;i<ask;i++){
42                     ans=(ans+((s[ask-1][i]%ask)*(p[i]%ask)))%ask;
43                 }
44                 cout<<ans<<"\n";
45             }
46             
47         }
48     }
49     return 0;
50 }

一道题竟然补了两天，浪费了好多时间QAQ