当前位置:首页 > 题解目录 > 正文内容

【题解】求次方和

亿万年的星光3年前 (2023-01-07)题解目录16560

【题目描述】

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




扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

八皇后2

【题目描述】会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 × 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。对于某个满足要求的8...

【题解】单词接龙

【题目描述】单词接龙是一个与我们经常玩的成语接龙相类似的游戏,现在我们已知一组单词,且给定一个开头的字母,要求出以这个字母开头的最长的“龙”(每个单词都最多在“龙”中出现两次),在两个单词相连时,其重...

【题解】游戏

【题目描述】上了半天的物理数学课,大家的脑子有点转不动了,下午的课表似乎看透了同学们的 心思,第一节就安排了体育课,CZ 中学的课表真是太有爱了,赞一个!午间休息后,文体 委员小 S 喊大家到教室外的...

【题解】滑翔翼

【题目描述】小T和小K都是OIER,入选省队后有幸去苏州参加JSOI集训,训练之余,他们相约一起去苏州乐园玩。苏州乐园里有一个非常热门的游乐项目叫双人滑翔翼。小T想和小K一起乘双人滑翔翼,但是排在他们...

【题解】感应门

【题目描述】感应门会在有人经过的时候自动打开,冷却d 秒后自动关闭。如果有人在感应门打开的状态下通过,那么冷却时间会重置,重新冷却d秒后再关闭。在一段时间内,有 n个人陆续通过了感应门,他们...

【题解】链表操作

【题目描述】给定一个N个数的数组,M次操作,每次操作为下列操作之一。求最后的数组。操作1:在第X个数之后插入一个数Y。操作2:删除第X个数。操作3:对区间[X,Y]进行排序。操作4:对区间[X,Y]进...