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

【题解】求次方和

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

【题目描述】

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




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

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

分享给朋友:

相关文章

【题解】密码截获

【题目描述】Catcher是MCA国的情报员,他工作时发现敌国会用一些对称的密码 进行通信,比如像这些ABBA,ABA,A,123321,但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。...

【题解】发工资

【题目描述】作为程序猿,最盼望的日子就是每月的9号了,因为这一天是发工资的日子,养家糊口就靠它了,呵呵但是对于公司财务处的工作人员来说,这一天则是很忙碌的一天,财务处的小李最近就在考虑一个问题:如果每...

【题解】括号匹配问题

【题目描述】在某个字符串(长度不超过100)中有左括号、右括号和大小写字母;规定(与常见的算数式子一样)任何一个左括号都从内到外与在它右边且距离最近的右括号匹配。写一个程序,找到无法匹配的左括号和右括...

【题解目录】友好城市

【题解目录】友好城市

【题目描述】Palmia国有一条横贯东西的大河,河有笔直的南北两岸,岸上各有位置各不相同的N个城市。北岸的每个城市有且仅有一个友好城市在南岸,而且不同城市的友好城市不相同。每对友好城市都向政府申请在河...

2021年市北区程序设计竞赛题(⼩学组)

最⼤值的相乘(maxx.cpp)【问题描述】第⼀⾏有x个正整数a1,a2,..,ax,第⼆⾏有y个正整数b1,b2,...,by,第三⾏有z个正整数c1,c2,...,cz,假设第⼀⾏的x个正整数中的...

【题解】分糖果问题

【题解】分糖果问题

【题目描述】一群孩子做游戏,现在请你根据游戏得分来发糖果,要求如下:每个孩子不管得分多少,起码分到一个糖果。任意两个相邻的孩子之间,得分较多的孩子必须拿多一些糖果。(若相同则无此限制)给定一个数组 a...