kuangbin14数论简单题

[A - Bi-shoe and Phi-shoe]

//my cpp
#include<cstdio>
#include<cmath>
using namespace std;
inline bool inprime(int x){
if(x<=2)return 1;
for(int i = 2; i <= sqrt(x)+1; i++){
if(x%i == 0)return 0;
}
return 1;
}
int main(){
int t=0,T;
scanf("%d",&T);
while(t++<T){
int n;
long long ans =0;
scanf("%d",&n);
for(int i = 0; i < n; i++){
int temp;
scanf("%d",&temp);
while(temp++){
if(inprime(temp)){ans+=temp;break;}
}
}
printf("Case %d: %lld Xukhan",t,ans);
}
return 0;
}
//dabiao
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 1000000;
int prime[maxn/10],sgn[maxn+7],cnt;
inline void initial(){
for(int i = 2; i < maxn + 7; i++){
if(!sgn[i]){
prime[cnt++] = i;
for(int j = i+i; j < maxn +7; j+=i){
sgn[j] = 1;
}
}
}
}
int main(){
initial();
int t;
scanf("%d",&t);
for(int i=1; i<=t;i++){
int n,x;
scanf("%d",&n);
long long ans=0;
for(int j=0; j<n; j++){
scanf("%d",&x);
ans+=prime[lower_bound(prime,prime+cnt,x+1)-prime];
}
printf("Case %d: %lld Xukhan",i,ans);
}
return 0;
}

[C - Aladdin and the Flying Carpet]

//shulun3
//解法： 
//主要利用公式: 
//一个整数ｎ可以表示为若干素数乘积：　n = p1^a1 * p2^a2*…*pm^am; 
//则 n 的正因数的个数可以表示为： num = (a1+1)*(a2+1)…(am+1);
//再减去1-min的
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<bitset>
#define CLR(a,v) memset(a,v,sizeof a)
using namespace std;
const int maxn = 1000005;
typedef long long ll;
bitset<maxn> vis;
int prime[maxn/10];
int p;
inline ll in()
{
ll res=0;char c;
while((c=getchar())<'0' || c>'9');
while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
return res;
}
void getPrime(){
for(int i = 2; i< maxn; i++){
if(!vis[i]){
prime[p++]=i;
for(int j = i+ i; j < maxn; j+=i){
vis[j] = 1;
}
}
}
}
int main(){
getPrime();
int T =in(),t=0;
while(t++<T){
ll area = in(),min = in();
if(min>=sqrt(area)){
printf("Case %d: %dn",t,0);
continue;
}
ll tmp = area;
int ans = 1;
for(int i = 0; 1LL*prime[i]*prime[i]<=area;i++){
int cnt = 0;
while(area%prime[i] == 0){
cnt++;
area/=prime[i];
}
ans*=(cnt+1);
}
if(area==1)ans>>=1;
for(int i = 1; i< min; i++)if(tmp%i==0)ans--;
printf("Case %d: %dn",t,ans);
}
return 0;
}

[E - Leading and Trailing]

//http://www.th7.cn/Program/cp/201607/904075.shtml
//shulun5+快速模模版+log
#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
typedef long long ll;
using namespace std;
int qmod(long long n , long long k){
ll res = 1;
while(k>0){
if(k&1)res=(res*n)%1000;
n = (n*n)% 1000;
k >>= 1;
}
return res%1000;
}
int qlog(long long n, long long k){
double a = log10(n+0.0)*k;
if(a<=3)return pow(10,a); //本句神坑。。。。
a-=(ll) a;
int ans = pow(10.0,a)*1000;
while(ans>=1000){ans/=10;}
return ans;
}
int main(){
int T,t=0;
scanf("%d",&T);
ll n,k;
while(t++<T){
scanf("%lld%lld",&n,&k);
printf("Case %d: %03d %03dn",t,qlog(n,k),qmod(n,k));
}
return 0;
}

[F - Goldbach`s Conjecture]

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<bitset>
#define maxn 10000005
using namespace std;
bitset<maxn> a;
int prime[maxn/10];
int cont=0;
inline void getPrime(){
for(int i = 2; i< maxn; i++){
if(!a[i]){
prime[cont++] = i;
for(int j = i+i; j < maxn ; j+=i)
a[j] = 1;
}
}
}
int main(){
getPrime();
int T,t=0;
scanf("%d",&T);
int ans;
while(t++<T){
ans=0;
int n;scanf("%d",&n);
for(int i = 0;prime[i]<=n/2;i++){
if(!a[n-prime[i]])ans++;
}
printf("Case %d: %dn",t,ans);
}
return 0;
}

[G - Harmonic Number (II)]

#include<cstdio>
#include<cmath>
using namespace std;
int main(){
int t=0,T;
scanf("%d",&T);
while(t++<T){
long long n;
scanf("%lld",&n);
int m = sqrt(n);
long long ans = 0;
for(int i = 1; i <=m; i++){
ans+=n/i;//oneprat
ans+=i*(n/i-n/(i+1));//anotheraprt
}
if(n/m==m)ans-=n/m;//ji
printf("Case %d: %lldn",t,ans);
}
return 0;
}

[H - Pairs Forming LCM]

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<bitset>
#define maxn 10000000
using namespace std;
bitset<maxn> a;
int prime[maxn/10];
int cont=0;
inline void getPrime(){
for(int i = 2; i< maxn; i++){
if(!a[i]){
prime[cont++] = i;
for(int j = i+i; j < maxn ; j+=i)
a[j] = 1;
}
}
}
int main(){
getPrime();
int T,t=0;
scanf("%d",&T);
while(t++<T){
long long n,ans = 1,m;
scanf("%lld",&n);
m = n;
for(int i = 0; prime[i] <= m/prime[i] && i < cont-1; ++i){
int cot = 0;
while(m%prime[i]==0){
cot++;
m/=prime[i];
}
ans*=(cot*2+1);
}
if(m>1)ans*=3;
ans = (ans+1)/2;
printf("Case %d: %lldn",t,ans);
}
return 0;
}

[I - Harmonic Number]

//正常做法：技巧打表
#include<cstdio>
#define maxn
1e8
using namespace std;
double a[(int)maxn/50+10];
void init(){
a[0] = 0;
for(int i = 0; i <= maxn/50+9; i++){
double tmp = 0;
for(int j = i*50+1; j <= i*50+50;j++){
tmp+=1.0/j;
}
a[i+1] = a[i]+tmp;
}
}
int main(){
init();
int t=0,T;
scanf("%d",&T);
while(t++<T){
double ans = 0;
int n;scanf("%d",&n);
ans+=a[n/50];
for(int i = n/50*50+1; i <= n; i++){
ans+=1.0/i;
}
printf("Case %d: %.10fn",t,ans);
}
return 0;
}
//数学大佬的做法
#include<cstdio>
#include<cmath>
//oulachangshu:0.57721566490153286060651209
using namespace std;
double a[10010];
double r=0.57721566490153;
int main(){
int n,i,cas=0,nn;
for(int i=1;i<=10000;i++)
a[i]=1.0/i+a[i-1];
scanf("%d",&nn);
while(cas++<nn){
scanf("%d",&n);
double i,ans=0;
printf("Case %d: %.10fn",cas,n>10000?1.0/(2*n)+log(n)+r:a[n]);
}
}

[J - Mysterious Bacteria]

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<bitset>
#define maxn 70000
#define CLR(a,v) memset(a,v,sizeof a)
using namespace std;
bitset<maxn> a;
int prime[maxn];
int cont=0;
int vis[maxn]={0};
inline void getPrime(){
for(int i = 2; i< maxn; i++){
if(!a[i]){
prime[cont++] = i;
for(int j = i+i; j < maxn ; j+=i)
a[j] = 1;
}
}
}
int main(){
getPrime();
int T,t=0;
scanf("%d",&T);
while(t++<T){
CLR(vis,0);
long long n,ans = 1,m;
scanf("%lld",&n);
int flag2= 0;
if(n<0){n=-n;flag2= 1;}
m = n;
int minx = 1000;
int lu = 0;
for(int i = 0; prime[i] <= m/prime[i] && i < cont-1; ++i){
if(m%prime[i]!=0){continue;}
while(m%prime[i]==0){
m/=prime[i];
vis[i]++;
}
lu = i;
minx=min(vis[i],minx);
}
if(m>1){printf("Case %d: 1n",t);continue;}
int flag = 0;
for(int i = 0; i<=lu;i++){
if(vis[i]==0)continue;
if(vis[i]%minx!=0){
flag=1;
break;
}
}
if(flag)minx=1;
if(flag2){
while(minx%2==0){
minx/=2;
}
}
printf("Case %d: %lldn",t,minx);
}
return 0;
}

[K - Large Division]

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
char input[300];
long long b;
int main(){
int t=0,T;
scanf("%d",&T);
while(t++<T){
scanf("%s%lld",input,&b);
if(b<0)b=-b;
long long ans=0;
int i=0;
for(;input[i]<'0' || input[i]>'9';i++);
for(;input[i]<='9' && input[i]>='0';i++){
ans=ans*10+(input[i]-'0');
ans%=b;
}
printf("Case %d: %sdivisiblen",t,(ans==0)?"":"not ");
}
return 0;
}

[L - Fantasy of a Summation]

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int mod,temp,n,k;
long long qpow(int n, int k){
long long ans=1;
while(k){
if(k&1){ans=ans*n%mod;}
n = n*n %mod;
k>>=1;
}
return ans%mod;
}
int main(){
int t=0,T;
scanf("%d",&T);
while(t++<T){
long long sum=0;
scanf("%d%d%d",&n,&k,&mod);
for(int i = 0; i<n ; i++){
scanf("%d",&temp);
sum+=temp;
sum%=mod;//漏了这句就wa了
}
sum*=k;
printf("Case %d: %lldn",t,(qpow(n,k-1)*sum)%mod);
}
return 0;
}

[M - Help Hanzo]

#include<cstdio>
using namespace std;
int pd[10000];//存放质数
bool judge[50010] = {0};//判断50000内的质数
void init(){
for(int i = 2; i <= 500; i++){
if(!judge[i]){
for(int j = i*i; j <= 50000; j+=i){
judge[j] = 1;
}
}
}
int j = 0;
for(int i = 2; i<= 50000; i++){
if(!judge[i])pd[j++]=i;
}
}
long long get(long long a, long long b){
long long sum = 0;//计数
bool sspd[200005]={0};
if(a<2){a=2;}//1不是
for(int i = 0; pd[i] <= b/pd[i]; i++){
long long j = pd[i]*(a/pd[i]);
if(j<a)j+=pd[i];
if(j==pd[i])j+=(long long)pd[i];//不标记质数
for(;j<=b; j+=pd[i])sspd[j-a]=1;//标记质数
}
for(int i = 0; i < b-a+1; i++){
if(!sspd[i])sum++;
}
return sum;
}
int main(){
init();
int t=0,T,a,b;
scanf("%d",&T);
while(t++<T){
scanf("%d%d",&a,&b);
printf("Case %d: %lldn",t,get(a,b));
}
return 0;
}

[N - Trailing Zeroes (III)]

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<bitset>
using namespace std;
int Find(int x){
int sum = 0;
while(x/5){
sum+=x/5;
x/=5;
}
return sum;
}
int main(){
int t=0,T,a;
scanf("%d",&T);
while(t++<T){
scanf("%d",&a);
int b = a*4/5*5;
while(Find(b)<a){
b+=5;
}
if(Find(b) != a)printf("Case %d: impossiblen",t);
else printf("Case %d: %dn",t,b);
}
return 0;
}

最后

以上就是羞涩小蜜蜂为你收集整理的kuangbin简单数论(上)kuangbin14数论简单题的全部内容，希望文章能够帮你解决kuangbin简单数论(上)kuangbin14数论简单题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。