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

【题解】求次方和

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

【题目描述】

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




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

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

分享给朋友:

相关文章

学生分组

【题目描述】有N组学生,给出初始时每组中的学生个数,再给出每组学生人数的上界R和下界L(L≤R),每次你可以在某组中选出一个学生把他安排到另外一组中,问最少要多少次才可以使N组学生的人数都在[L,R]...

【题解】装满杯子需要的最短总时长

【题目描述】现有一台饮水机,可以制备冷水、温水和热水。每秒钟,可以装满 2 杯 不同 类型的水或者 1 杯任意类型的水。给你一个下标从&nb...

【题解】画百钱买百鸡

【题目描述】鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡。问鸡翁、鸡母、鸡雏各几何?#include<iostream> using namespace ...

2021年市北区程序设计竞赛试题(初中组)

2021年市北区程序设计竞赛试题(初中组)

1.开关灯(light.cpp)【题目描述】某实验室共有n盏灯,灯的编号为1~n,每盏灯的初始状态是关闭的。现在有m位学生,每位学生可以前去抽取一张带数字的卡片,其数字为Ai,然后依次将自己手中的数字...

【题解】零花钱

零花钱(money.cpp) 【问题描述】 商店里有一件玩具,今天你偶然得知:这件玩具在后⾯的n天里每天的定价(价格可能每天都会改 变),你买了这件玩具后可以以当天的价格卖给商店,...

【题解】王国比赛

【题解】王国比赛

【题目描述】智慧之王 Kri 统治着一座王国。 这天 Kri 决定举行一场比赛,来检验自己大臣的智慧。 比赛由 n道判断题组成,有 m位大臣参加。现在你已经知道了所有大臣的答题情况,但尚未拿到答...