填坑-回溯-预习之素数大总结

杨鹏伟

发布于 2020-09-11 00:07:10

3960

发布于 2020-09-11 00:07:10

文章被收录于专栏：ypw

正值肺炎，无聊不如填坑~A水题维持生计

A.分拆素数和 HDU 2098

把一个偶数拆成两个不同素数的和，有几种拆法呢？

思路：判断当前 i 是否为素数跟 n-i 是否为素数即可

#include<bits/stdc++.h>

using namespace std;

bool is(int x){
	if(x == 2) return true;
	else{
		for(int i=2; i * i <= x;i++){
			if(x % i == 0){
				return false;
			}
		}
		return true;
	}
}

int main(){
	 int n;
	 while(cin>>n && n){
	 	int num = 0;
	 	for(int i=2;i<=(n-1)/2;i++){
	 		if(is(i) && is(n-i)){
	 			num++;
			 }
		 }
		 cout<<num<<endl;
	 }
	return 0;
}

B - 素数判定 HDU - 2012 对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<y<=50)，判定该表达式的值是否都为素数。

思路：很简单，注意输出不是YES跟NO了，让我W了一次！

#include<bits/stdc++.h>

using namespace std;

bool is(int x){
	if(x == 2) return true;
	else{
		for(int i=2; i * i <= x;i++){
			if(x % i == 0){
				return false;
			}
		}
		return true;
	}
}

int main(){
	int n,m;
	int res;
    while(cin>>n>>m&&(n+m)){
    	int flag = 0;
        for(int i=n;i<=m;i++){
        res = i*i+i+41; 
		if(!is(res)){
			flag = 1;
			break;
		}
		else{
			continue;
		}
	}
	if(!flag)  
	 cout<<"OK"<<endl;
	else
	 cout<<"Sorry"<<endl;
	
		
	}
	return 0;
}

C - Rightmost Digit HDU - 1061

凡凡说：“我的数学，那是天下无敌，你们一个能打的都没有！” 凉凉听了，很不服气：“那我要考考你，N个N相乘的最后一位数字是多少？

思路：数据范围大！所以暴力肯定是不行得！复习了快速幂！注意用 long long ，不然会W

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll qp(ll a,ll s,ll mod){
	ll res = 1;
	while(s){
		if(s & 1) res = res * a % mod;
		a = a* a % mod;
		s >>= 1;
	}
	return res;
}


int main(){
	int t;
	cin>>t;
	while(t--){
		ll n;
		cin>>n;
		cout<<qp(n,n,10)<<endl;
	} 
	return 0;
}

D - Key Set HDU - 5363 题意：在非空子集里面找到和为偶数得子集得个数！

思路：找规律

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mod = 1000000000+7;
const int maxn = 1e5; 

int a[maxn];

ll qp(ll a,ll n){
	ll res = 1;
	while(n){
		if(n & 1) res = res * a % mod;
		 a = a* a %mod;
		 n >>= 1;
	}
	return res;
}


int main(){
	ll ans  = 0;
	ll t;
	cin>>t;
	ll n;
    while(t--){
		cin>>n;
		ans = qp(2,n-1)-1;
		cout<<ans<<endl;
	}
	return 0;
}

E - Pseudoprime numbers POJ - 3641

思路：问p是不是伪素数。伪素数条件：①p不是素数。② ap = a (mod p)。

#include<iostream>
using namespace std;
typedef long long ll;


ll qp(ll b,ll n,ll mod){
	ll res = 1;
	while(n){
		if(n & 1) res = (res * b) % mod;
		 b = (b* b)% mod;
		 n >>= 1;
	}
	return res;
}

bool is(ll x){
	if(x == 2)  return true;
	else{
		for(ll i=2; i * i <= x;i++){
			if(x % i == 0){
				return false;
			}
		}
		return true;
	}
}


int main(){
	ll a,p;
	while(cin>>p>>a && a|| p){
		if(is(p)){
			cout<<"no"<<endl;
		} 
		else{
			if(qp(a,p,p) == a)
			  cout<<"yes"<<endl;
			else
			  cout<<"no"<<endl;
		}
	}
	return 0;
}

F - Raising Modulo Numbers

题意：就是多组数据的幂的累加。

题看起来很吓人，但先看数据及式子就能猜出题意了

#include<bits/stdc++.h>
#define maxn 45005
using namespace std;

typedef long long ll;

ll qp(ll a,ll n,ll mod){
	ll res =1;
	while(n){
		if(n &1) res = (res * a) %mod;
		a = (a*a) %mod;
		n >>= 1; 
	}
	return res;
}


int main(){
	int t;
	cin>>t;
	while(t--){
		ll n;
		ll x,y;
		ll mod;
		cin>>mod;
		cin>>n;
		ll sum = 0;
		for(int i=0;i<n;i++){
			cin>>x>>y;
			sum += qp(x,y,mod);
			sum %= mod;
		}
		sum %= mod;
		cout<<sum<<endl;
	}
	return 0;
}

G - 人见人爱A^B

求A^B的最后三位数表示的整数。说明：A^B的含义是“A的B次方”

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll qp(int a,int n,int mod){
	ll res = 1;
	while(n){
		if(n&1) res = (res*a)%mod;
		a = (a*a)%mod;
		n >>= 1;
	}
	return res;
}

int main(){
	int n,m;
	while(cin>>n>>m&&(n+m)){
		cout<<qp(n,m,1000)<<endl;
	}
	return 0;
}

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

原始发表：2020/02/06 ，如有侵权请联系 cloudcommunity@tencent.com 删除

key