以下题目涉及知识有 欧拉函数、素数筛、算数基本定理(唯一分解定理)

因为数论之前没咋学,欧拉函数还是这两天补的,又要考试,时间不够,所以大多数都是直接搜题解做的,本来信誓旦旦好好写一些题解巩固一下的,发现越写越累,索性直接搬来别人的优质题解算了🤔

一定记得素数筛时 isp 数组要用 bool,bool 只占用一个字节,int4 个会爆内存,卡死我了,我说咋一直爆内存

# Bi-shoe and Phi-shoe

题意
给定 N 个数,让你求欧拉函数值大于等于这 N 个数的的那个数的最小数值之和(这里 1 的欧拉函数值很特殊,设置为 0,因为小于 1 且与 1 互质的数量为 0)
例如:
N==2
1 2
则答案为 4 == 1+3
思路
要求的是欧拉函数值大于等于给定数的最小数,那么我们就要让这个数对应的欧拉函数值尽可能大一点,什么情况下一个数的欧拉函数值最大呢?很明显是素数时!一个素数的欧拉函数值就等于这个数减一,从这里我们就能推出来最小的那个对应欧拉函数值大于等于给定数的那个数最小就是这个给定数后面的那个素数,例如: 10 对应的就是 11 ,12 对应 13 ,14 对应 17,11,13,17 就是所要求的最小的三个数,由此思路就明确了
思路 2
还可以用筛法求 1~N 的欧拉函数,然后打表每个欧拉函数值的最优解,再取和最小

# CODE-1

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAXN = 1e7+10;
const int MOD = 1e9;
int pr[MAXN/10], tail = 0; 
bool isp[MAXN];
void prime() {  //一个素数筛
    isp[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        if (!isp[i]) pr[++tail] = i;
        for (int j = 1; i <= MAXN/pr[j]; j++) {
            isp[i * pr[j]] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}
int main()
{
	ios;
	prime();
  int t,kase=0; cin>>t;
  while(t--){
    int n; cin>>n;
    ll sum=0;
    for(int i=1;i<=n;i++){
      int x; cin>>x;
      for(int j=x+1; ;j++){ //找到给定数字后面的那个素数累加到sum里面
        if(!isp[j]){
          sum+=j;
          break;
        }
      }
    }
    cout<<"Case "<<++kase<<": "<<sum<<" Xukha"<<endl;
  }
  return 0;
}

# CODE-2

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN = 1e6+100;
const int MOD = 1e9;
int pr[MAXN/10],tail;
int phi[MAXN],ans[MAXN];
bool isp[MAXN]; 
void euler()
{
	phi[1]=0;
	for(int i=2;i<MAXN;i++){
		if(!isp[i]){
			pr[++tail]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=tail&&i*pr[j]<MAXN;j++){
			isp[i*pr[j]]=1;
			if(i%pr[j]==0){
				phi[i*pr[j]]=phi[i]*pr[j];
				break;
			}
			else phi[i*pr[j]]=phi[i]*phi[pr[j]];
		}
	}
	int cur=0;
	for(int i=2;i<MAXN;i++){  //核心代码,这里一定要保证ans是递增的,因为要往后走找更大的欧拉函数值
		if(phi[i]>cur&&ans[phi[i]]==0){ //ans下标代表欧拉函数值,储存的是该欧拉函数值对应的数字,ans[]==0起到防止相同欧拉函数值的两个数后面那个数把前面的覆盖了
			ans[phi[i]]=i;
			cur=phi[i]; //记得更新cur 因为要求最小的那个数字
		}
	}
}
int main()
{
	ios; ll n;
	euler();
	int t,kase=0;
	cin>>t;
	while(t--){
		ll sum=0;
		int n; cin>>n;
		for(int i=1;i<=n;i++){
			int x; cin>>x;
			for(int j=x; ;j++){
				if(ans[j]>0){
					sum+=ans[j];
					break;
				}
			}	
		}
		cout<<"Case "<<++kase<<": "<<sum<<" Xukha"<<'\n';
	}
    return 0;
}

# Aladdin and the Flying Carpet

题意
给出矩形面积 S,和组成该矩形的边的最小值,问这种面积为 S 的矩形有几种
比如样例 12 2,矩形面积为 12,组成这样矩形的最小边为 2,共有 2 种这样的矩形(2, 6),(3, 4)(这些边都大于或等于 2,其中(2,6)和(6,2)是同一种)
思路
这道题用到了唯一分解定理:N = p1a1 p2a2 * p3a3 * ... pnan (其中 p1、p2、... pn 为 N 的因子,a1、a2、... 、an 分别为因子的指数)
N 的因子个数公式: M = (1 + a1)
(1 + a2)* (1 + a3)* ...*(1 + an);
用唯一分解定理求出 ab 的因子个数,但题要求的是满足条件的因子对数,所以最终所求的因子个数需要除以 2,然后再将不满足的减去
该题要用到筛选素数来缩短时间(减少循环次数)来防止 TLE
疑问
两个因子可以一样啊,25 ==5 ,5,那 num 不是应该 =(num+1)/2 吗?这道题自动排除了 1 和数本身的情况?

# CODE

#include<queue>
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1e6+5;
bool isp[MAXN];
int pr[MAXN/10],tail;
int prime(){
	isp[1]=1;
	for(int i=2;i<MAXN;i++){
		if(!isp[i]) pr[++tail]=i;
		for(int j=1;j<=tail&&i*pr[j]<MAXN;j++){
			isp[i*pr[j]]=1;
			if(i%pr[j]==0) break;
		}
	}
}
ll fun(ll n){ //找出n的因子数量
	ll ans=1;
	for(ll i=1;i<=tail&&pr[i]*pr[i]<=n;i++){
		if(n%pr[i]==0){
			ll e=0;
			while(n%pr[i]==0){
				e++;
				n/=pr[i];
			}
			ans*=(1+e);//算数基本定理的经典问题:求一个数的因子数量
		}
	}
	if(n>1) ans*=2;
	return ans;
}
int main()
{
	prime();
  int t,kase=0;
  scanf("%d",&t);
  while(t--){
    kase++;
    ll s,a;
    scanf("%lld%lld",&s,&a);
    if(a*a>s){
        printf("Case %d: 0\n", kase);
        continue;
    }
    ll num=fun(s);
    num/=2; //两个因子为一对,除2
    for(ll i=1;i<a;i++){
      if(s%i==0) num--;
    }
    printf("Case %d: %lld\n", kase, num);
	}
    return 0;
}

# Goldbach`s Conjecture

题意
给出几组测试数据,每组给出一个 n,问 n 能被分成几对素数的和。
思路
少有的水题,素数筛一下,遍历素数,然后每次查看 sum - 该素数是不是素数是的话答案加一,遍历过半就可以退出了

# CODE

#include <stdio.h>
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN=1e7+20;
bool isp[MAXN];
int pr[700000];
int t,k=0;
void prime()
{
    isp[1]=1;
    for(int i=2;i<=MAXN;i++){
        if(!isp[i]){
            pr[++k]=i;
            for(int j=i+i;j<=MAXN;j+=i){
                isp[j]=1;
            }
        }
    }
    return ;
}
int main()
{
	prime();
    int t,kase=0;
    scanf("%d",&t);
    while(t--){
    	int n,cnt=0;
    	scanf("%d",&n);
    	for(int i=1;i<=n/2;i++){
    		if(pr[i]>=n/2+1) break;
    		if(!isp[n-pr[i]]) cnt++;
		}
		printf("Case %d: ",++kase);
		cout<<cnt<<'\n';
	}
    return 0;
}

# Pairs Forming LCM

题意
在 1~n 中有多少对数满足 lcm (a,b)==n
思路
gcd (a,b)=p1 min(a1,b1) * p2min(a2,b2) * .......... *pnmin(an,bn)
lcm(a,b)=p1 max(a1,b1) * p2max(a2,b2) * .......... *pnmax(an,bn)
先对 n 素因子分解,n = p1e1 * p2e2 * .......... *pkek
lcm(a,b)=p1 max(a1,b1) * p2max(a2,b2 * .......... *pkmax(ak,bk)

所以,当 lcm (a,b)==n 时,max (a1,b1)==e1,max (a2,b2)==e2,…max (ak,bk)ek
当 ai == ei 时,bi 可取 [0, ei] 中的所有数 有 ei+1 种情况,bi
ei 时同理。
那么就有 2 (ei+1) 种取法,但是当 ai = bi = ei 时有重复,所以取法数为 2 (ei+1)-1=2ei+1。
除了 (n, n) 所有的情况都出现了两次 那么满足 a<=b 的有 (2
ei + 1)) / 2 + 1 个

# CODE

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAXN = 1e7+10;
const int MOD = 1e9;
int pr[MAXN/10], tail = 0;
bool isp[MAXN];
void prime() {
    isp[1] = 1;
    for (int i = 2; i <= MAXN; i++) {
        if (!isp[i]) pr[++tail] = i;
        for (int j = 1; j<=tail &&i * pr[j] <= MAXN; j++) {
            isp[i * pr[j]] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}
int main()
{
	prime();
    int t,kase=1;
    cin>>t;
    for( ;kase<=t;kase++){
    	ll n; cin>>n;
    	int ans=1;
    	for(int i=1;i<=tail&&pr[i]*pr[i]<=n;i++){
    		if(n%pr[i]==0){
    			int e=0;
    			while(n%pr[i]==0){
    				e++;
    				n/=pr[i];
				}
				ans*=(2*e+1);
			}
		}
		if(n>1) ans*=(2*1+1);
		printf("Case %d: %d\n",kase,(ans+1)/2);
	}
  return 0;
}

# Mysterious Bacteria

题意
给你一个数 x = bp, 求 p 的最大值
思路
p = gcd (x1, x2, x3, ... , xs) xi 是拆分后的指数
比如: 24 = 23*31,p 应该是 gcd (3, 1) = 1, 即 24 = 241
324 = 34*22,p 应该是 gcd (4, 2) = 2, 即 324 = 182
~~ 注意:~~ 本题有一个坑,就是 x 可能为负数,如果 x 为负数的话,x = b^q, q 必须使奇数,所以将 x 转化为正数求得的解如果是偶数的话必须将其一直除 2 转化为奇数
疑问
为什么代码标记的地方的那个 n 不开 ll 会超时呢?ll 转换成负数快?

# CODE

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN = 1e5+10;
const int MOD = 1e9;
int pr[MAXN/10], tail = 0;
bool isp[MAXN];
void prime() {
    isp[1] = 1;
    for (int i = 2; i < MAXN; i++) {
        if (!isp[i]) pr[++tail] = i;
        for (int j = 1; i <= MAXN/pr[j]; j++) {
            isp[i * pr[j]] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}
int gcd(int a,int b){
	if(a%b==0) return b;
	else return gcd(b,a%b);
}
int main()
{
	ios;
	prime();
    int t,kase=0; cin>>t;
    while(t--){
    	ll n; cin>>n;  //这里n必须开成ll否则会超时
    	int flag=0,ans=0;
    	if(n<0){
    		n=-n;  //n如果不开成ll的话这里会卡住
    		flag=1;
		}
    	for(int i=1;i<=tail&&pr[i]*pr[i]<=n;i++){
    		if(n%pr[i]==0){
				int e=0;
    			while(n%pr[i]==0){
    				e++;
    				n/=pr[i];
				}
				if(ans==0) ans=e;
				else ans=gcd(ans,e);
			}
		}
    	if(n>1) ans=gcd(ans,1);
    	if(flag==1){
    		while(ans%2==0){
    			ans/=2;
			}
		}
    	cout<<"Case "<<++kase<<": "<<ans<<'\n';
	}
    return 0;
}

# Large Division

题意
给你两个数 a,b,让你求出来 a 是否能够被 b 整除。
思路
需要注意的是数字 a 太大了,所以要用数组来存储,同时还要注意数字 b 可能超出了 int 范围,要用 long long int,考的其实就是除法的模拟

# CODE

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
typedef long long ll;
const int MAXN=1e6+10;
char a[MAXN];
int main()
{
    int t,kase=0;
    scanf("%d",&t);
    while(t--){
    	memset(a,0,sizeof a);
    	ll b;
    	scanf("%s",a);
    	scanf("%lld",&b);
    	if(b<0) b=-b;
    	ll x=0,len=strlen(a);
    	for(int i=0;i<len;i++){
    		if(a[i]=='-') continue;
    		x=(x*10+a[i]-'0')%b;
		}
		if(x==0) printf("Case %d: divisible\n",++kase);
    	else printf("Case %d: not divisible\n",++kase);
    	
	}
    return 0;
}

# Help Hanzo

题意
求区间 a,b 内素数的数量
思路
由于 b 极大,所以打表会爆内存。但并不意味着放弃打表,我们可以先打一个小点的素数表出来,如果 b 在这个表内直接二分找一下 a,b 就可以了。否则利用到 b-a<=100000 这个性质,可以开一个这么大的桶下标表示为 j-a 来筛选 a-b 内的素数,这样就用到我们之前的小素数表来筛选了。

# CODE

#include<iostream>
#include<cstdio>
#include<set>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
typedef long long ll;
using namespace std;
const int MAXN=1e6+10;
bool vis1[MAXN],vis2[MAXN];
int pr[MAXN],cnt;
int prime(){
	for(int i=2;i<MAXN;i++){
		if(vis1[i]==0){
			pr[cnt++]=i;
			vis1[i]=1;
		}
		for(int j=0;j<cnt&&pr[j]*i<MAXN;j++){
	  		vis1[i*pr[j]]=1;
	  		if(i%pr[j]==0) break;
		}
	}
}
int main()
{
	prime();
  	int t,kase=1;
  	cin>>t;
  	while(t--){
		ll a,b,ans=0;
		cin>>a>>b;
		if(b<=MAXN){
		    int loab=lower_bound(pr,pr+cnt,b)-pr; 
		    if(pr[loab]>b) loab-=1;
		    int loaa=lower_bound(pr,pr+cnt,a)-pr;
		    ans=loab-loaa+1;
		}
		else{
		    memset(vis2,0,sizeof(vis2));
		    for(int i=0;i<cnt;i++){
		        ll k=(a%pr[i]==0)?a/pr[i]:a/pr[i]+1;  
		        for(ll j=k*pr[i];j<=b;j+=pr[i]) vis2[j-a]=1;
		    }
		    for(ll i=a;i<=b;i++){
		        if(!vis2[i-a]) ans++;
		    }
		}
		cout<<"Case "<<kase++<<": "<<ans<<endl;
  	}
}

# GCD - Extreme (II)

题意
求在 1-n 之间所有任意两个数的的最大公因数的和。
题解
因为让求的 1-n 区间里任两个数的最大公因数之和,所以假设 gcd (n,m)=z,在这里,因为 n 和 m 的范围都是超级大,所以,不能枚举 n,m,但是可以枚举 m,z,或者 n,z。
具体思路是:假设 gcd (x,y)=1, 那么当执行到 x,y 的时候,最后的和都要加 1,那么相应的,执行到 2x,2y 时,最后的和都要加 2,以此类推,执行到 kx,ky 的时候最后的和都要加 k,那么这些一切的根源都归咎于 gcd (x,y)=1,所以才有了上面那一句话,枚举 n,z(n,m 选其一,无所谓的),这里的 z 就是上面的 1,2,。。k。枚举 z 的问题解决了,那么轮到 n 了,枚举 n,假设一个值为 num,那么 num 代表与 n 的最大公因数是 z(1,2,3,,,,k)的个数,这里的 z 有好多值,但是任何的 z(大于 1)都可以有最根本的 gcd(x,y)推出,所以算出只需要算出 z=1 时 num 的值就可以了,这个时候,就会想到欧拉函数值(小于 n 的数里与 n 互质的个数)。然后,这道题算是结束了。

# CODE

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN = 4e6+10;
const int MOD = 1e9;
int pr[MAXN/10],tail;
ll a[MAXN],phi[MAXN];
bool isp[MAXN]; 
void euler()
{
	phi[1]=1;
	for(int i=2;i<MAXN;i++){
		if(!isp[i]){
			pr[++tail]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=tail&&i*pr[j]<MAXN;j++){
			isp[i*pr[j]]=1;
			if(i%pr[j]==0){
				phi[i*pr[j]]=phi[i]*pr[j];
				break;
			}
			else phi[i*pr[j]]=phi[i]*phi[pr[j]];
		}
		for(int j=1;i*j<MAXN;j++){
			a[i*j]+=phi[i]*j;
		}
	}
}
int fun(int n){
	int ans=n;
	if(n==1) return 1;
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			ans=ans/i*(i-1);
			while(n%i==0) n/=i;
		}
	}
	if(n>1) ans=ans/n*(n-1);
	return ans;
}
int main()
{
	ios; ll n;
	euler();
	for(int i=1;i<MAXN;i++){
		a[i]+=a[i-1];
	}
	while(~scanf("%lld",&n)&&n){
		printf("%lld\n",a[n]);
	}
    return 0;
}

# Farey Sequence

题意
给出式子 F F 中分子分母互质,且分子小于分母
例:

F2 = {1/2}
F3 = {1/3, 1/2, 2/3}
F4 = {1/4, 1/3, 1/2, 2/3, 3/4}
F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}
求解 fn 的元素个数
题解
本题就是求解欧拉函数值的前 n 项和,模板题,筛一下就行了

# CODE

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN = 1e6+100;
const int MOD = 1e9;
int pr[MAXN/10],tail;
ll phi[MAXN];
bool isp[MAXN]; 
void euler()
{
	phi[1]=0;
	for(int i=2;i<MAXN;i++){
		if(!isp[i]){
			pr[++tail]=i;
			phi[i]=i-1;
		}
		for(int j=1;j<=tail&&i*pr[j]<MAXN;j++){
			isp[i*pr[j]]=1;
			if(i%pr[j]==0){
				phi[i*pr[j]]=phi[i]*pr[j];
				break;
			}
			else phi[i*pr[j]]=phi[i]*phi[pr[j]];
		}
	}
}
int main()
{
	ios; ll n;
	euler();
	for(int i=1;i<MAXN;i++){
		phi[i]+=phi[i-1];
	}
	while(cin>>n){
		if(n==0) break;
		cout<<phi[n]<<'\n';
	}
    return 0;
}

# Maximum GCD

题意
给定一串数,求两两 gcd 最大值
思路
这道题考的其实是读入,两个数之间空格可以有多个!!!

# CODE

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAXN = 1e5;
const int MOD = 1e9;
int pr[MAXN], isp[MAXN], tail = 0;
void prime() {
    isp[1] = 1;
    for (int i = 2; i <= 17000; i++) {
        if (!isp[i]) pr[++tail] = i;
        for (int j = 1; i * pr[j] <= 17000; j++) {
            isp[i * pr[j]] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}
int a[110];
char c[100000];
int main()
{
    int n,tail=0;
    scanf("%d\n",&n);
    while(n--){
    	gets(c); tail=0;
    	int len=strlen(c);
        for(int i=0; i<len; i++){
            int sum=0;
            while(i<len&&c[i]!=' '){
                sum=sum*10+c[i]-'0';
                i++;
            }
            a[++tail]=sum;
        }
        int maxx=-1e9;
		for(int i=1;i<tail;i++){
			for(int j=i+1;j<=tail;j++){
				maxx=max(maxx,__gcd(a[i],a[j]));
			}
		}
		cout<<maxx<<endl;
	}
    return 0;
}

# Primes

题意
给定一个数判断是不是素数
思路
这个就太水了,坑我的就是题目最多有 250 组数据,我说咋一直超时。。

# CODE

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAXN = 1e5;
const int MOD = 1e9;
int pr[MAXN], isp[MAXN], tail = 0;
void prime() {
    isp[1] = 1;
    for (int i = 2; i <= 17000; i++) {
        if (!isp[i]) pr[++tail] = i;
        for (int j = 1; i * pr[j] <= 17000; j++) {
            isp[i * pr[j]] = 1;
            if (i % pr[j] == 0) break;
        }
    }
}
int main()
{
	prime(); 
    int n, kase = 0;
    for(int k=1;k<=250;k++){
    	scanf("%d",&n);
        if (n <= 0) break;
        if (n <= 2) {
            printf("%d: %s\n", ++kase, "no");
            continue;
        }
        printf("%d: ",++kase);
        if (isp[n]) printf("%s\n", "no");
        else printf("%s\n", "yes");
    }
    return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝