数论基础专题小结

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

---

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:](http://acm.hust.edu.cn/vjudge/contest/view.action?cid=70017#problem/F)

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

#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);
    }
}```