acwing5579 增加模数
先上题目:
那么这道题目就是典型的快速幂 ，本人有写过快速幂的模板，链接在这:快速幂模板
在我用模板写完了之后，我的模板套用如下:
#include <iostream>using namespace std;int t;int power(int a,int b,int p)
{int res=1%p;for(;b;b>>=1){if(b&1) res=(long long)res*a%p;a=(long long)a*a%p; }return res;
}int main()
{cin>>t;while(t--){int m,h;cin>>m;cin>>h;int res=0;for(int i=0;i<h;i++){int a,b;cin>>a>>b;res=(res+power(a,b,m))%m;}cout<<res<<endl;}return 0;
}
结果TLE了，发现没过的样例我有一半来不及输出，我突然意识到我的io(cin和cout)可能拖累了我，我随即加上了ios::sync_with_stdio(false);cin.tie(0):cout>tie(0);
结果又是TLE，而且这次只剩下6个答案来不及输出出来！！！！(╯°□°）╯︵ ┻━┻
我开始翻看题解，发现2024年提供的题解基本上就是我这个模板，但是ctrl+c/v过来的情况就是现在都TLE了，我猜测这个题目之后的数据应该是加强了，但我确实不知道在哪里优化了，于是又翻看了两个2025年的题解，发现其中说到:大量运算时 尤其是%运算 *运算 long long 的开销会高于 int 会更耗时,m < 45000 也就是运算时最多只是44999 * 44999。而且我用计算机按了一下发现45000^2非常完美的贴近int却没有爆int，也就是说我们模板中的res=(long long)res*a%p;和a=(long long)a*a%p;便不用加入(long long)强制类型转换，使用更加高效的int类型做运算，可以提高一点效率讲剩下的6个答案计算出来随后代码如下：
#include <iostream>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)using namespace std;int t;int power(int a,int b,int p)
{IOS;int res=1%p;for(;b;b>>=1){if(b&1) res=res*a%p; //注意这里因为res和a根据题目数据范围都必然小于 45000，而45000^2并不会爆int，所以这里不用加上(long long)a=a*a%p; //大量运算时 尤其是%运算 *运算 long long 的开销会高于 int 会更耗时,m <= 4500 也就是运算时最多只是4499 * 4499}return res;
}int main()
{cin>>t;while(t--){int m,h; cin>>m>>h;int res=0;for(int i=0;i<h;i++){int a,b;cin>>a>>b;res=(res+power(a,b,m))%m;}cout<<res<<endl;}return 0;
}
结果它这次WR了，emm然后我自己比对题解发现大佬们都讲传入power中的基数也就是a都提前mod了一个m，而我也尝试了一下, 代码如下(只是比上面这个传入power中的a是不一样的)：
#include <iostream>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)using namespace std;int t;int power(int a,int b,int p)
{IOS;int res=1%p;for(;b;b>>=1){if(b&1) res=res*a%p; //注意这里因为res和a根据题目数据范围都必然小于 45000，而45000^2并不会爆int，所以这里不用加上(long long)a=a*a%p; //大量运算时 尤其是%运算 *运算 long long 的开销会高于 int 会更耗时,m <= 4500 也就是运算时最多只是4499 * 4499}return res;
}int main()
{cin>>t;while(t--){int m,h; cin>>m>>h;int res=0;for(int i=0;i<h;i++){int a,b;cin>>a>>b;res=(res+power(a%m,b,m))%m;}cout<<res<<endl;}return 0;
}
然后就过了φ(*￣0￣)，但是我还是没想明白为什么不加(long long)的时候a不提前mod上m的话会错，有大佬能解释吗，我们可以探讨探讨。