数论基础专题小结

mythsman

发布于 2022-11-14 14:24:55

1660

发布于 2022-11-14 14:24:55

这个专题很杂，牵涉到很多数学公式和一些优化方法，还是要根据不同的题目来积累经验。

LightOJ 1282 Leading and Trailing: 这道题牵涉到求一个大数的前几位和后几位的方法，前者主要是通过对数进行处理，后者通过快速取模。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int  powMod(int a,int n,int mod){
	int  ans=1;
	while(n>0){
		if(n&1){
			ans=ans*a%mod;
		}
		n>>=1;
		a=a*a%mod;
	}
	return ans;
}
int getHead(int n,int k){
	 return pow(10,2+fmod(k*log10(n),1));
}
int main(){
	int  t;
	scanf("%d",&t);
	for(int  i=1;i<=t;i++){
		int  n,k;
		scanf("%d%d",&n,&k);

		printf("Case %d: %d %03dn",i,getHead(n,k),powMod(n%1000,k,1000));
	}
}

LightOJ 1259 Goldbach`s Conjecture:

这道题主要是判断素数和素数表相结合，用素数表提高枚举效率，通过判断素数表提高判断的效率。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
vector<int>prime;
bool p[10000004];
int main(){
	int tt;
	prime.clear();
	memset(p,0,sizeof p);
	for(int i=2;i<=10000000;i++){
		if(p[i]==0){
			prime.push_back(i);
			for(int j=2;i*j<=10000000;j++){
				p[j*i]=1;
			}
		}
	}
	scanf("%d",&tt);
	for(int t=1;t<=tt;t++){
		int n;
		scanf("%d",&n);
		int ans=0;
		for(int i=0;prime[i]*2<=n;i++){
			if(p[n-prime[i]]==0){
				ans++;
			}
		}
		printf("Case %d: %dn",t,ans);
	}
}```

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

效率