这个专题很杂,牵涉到很多数学公式和一些优化方法,还是要根据不同的题目来积累经验。
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);
}
}```