【题解】求次方和
【题目描述】
求解 (2^0 + 2^1 + 2^2+ ... + 2^n) % 2333
【输入描述】
一行，一个整数n。
【输出描述】
一行，表达式的正确结果
【样例输入】
2
【样例输出】
7
【题目分析】
从题目上看，并不难，只要循环相乘后在模2333就可以求出结果来了。
如果考虑到程序中的数据范围，那么大概率是要超int范围的
【参考代码1】
#include<bits/stdc++.h>
using namespace std;
int main()
{
int ans=0;
int n=1000;
for(int i=0;i<=n;i++){
int temp=1;
for(int j=1;j<=i;j++){
temp=temp*2;
}
ans=ans+temp;
}
cout<<(ans%2333);
return 0;
}上面这段参考代码是大部分人能写出来的版本，但是这段代码在运算过程中非常容易超int范围，所以需要改进一下，我们用数论里的知识进行改进。
用的是下面两个公式：
（a+b）%p=(a%p+b%p)%p; （a*b）%p=a%p*b%p;
那么我们可以把程序改成下面这样：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int ans=0;
int n=1000;
for(int i=0;i<=n;i++){
int temp=1;
for(int j=1;j<=i;j++){
temp=temp*2;
temp=temp%2333; //边乘边模!!!
}
ans=ans+temp;
ans=ans%2333; //边加边模!!!
}
cout<<(ans%2333);
return 0;
}例题2：
【题目描述】
已知S(n)=n^5，求S(n)模3的值
【输入描述】
一行，一个整数n。（1<n<1000000）。
【输出描述】
一行，正确的结果。
【样例输入】
1
【样例输出】
1
【题目分析】
因为int的范围最多是10^9。long long 的范围最多表示10^18。这里n^5次方非常容易超过long long，超过了long long一般有两个思路，要么用高精度，要么缩减运算范围。
本题有明显模运算，这提示我们不用考虑高精度了。
n^5=n*n*n*n*n。 所以 (n^5)%3=( (n%3)*(n%3)*(n%3)*(n%3)*(n%3) ) % 3。然后就可以套公式了
【参考代码】
#include<bits/stdc++.h>
using namespace std;
int main() {
int n=999998;
int ans=1;
for(int i=1; i<=5; i++) {
int temp=n%3;
ans=ans*temp;
}
cout<<(ans%3); //最后还要模一次3
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。