【题目描述】

    求解 (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
}