题解系列012 + 比赛系列002 | CSDN 第五届编程竞赛题解 + 建议

题目分析

第一题

网上关于

我们知道，任何一个正整数 $n$ 均可以用唯一素因数分解表示（百度百科），即 $$n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$$ 这里 $p_1,\cdots ,p_k$ 均为素数且我们不妨设 $p_1<p_2<\cdots <p_k$。我们熟知，$n$ 的正因数个数 $d(n)=\prod _{i=1}^k({\alpha }_i+1)$，故我们相当于是要对 $k$ 同样做出素因子分解。

调整一

我们先固定 ${\alpha }_1,\cdots ,{\alpha }_k$，改动 $p_1,\cdots ,p_k$. 我们设最小的 $k$ 个素数依次为 $2=q_1<q_2<\cdots <q_k$, 则显然有 $p_i\ge q_i(\forall 1\le i\le k)$, 因此可以将 $n=\prod _{i=1}^k{p}_i^{{\alpha }_i}\stackrel{\text{调整到}}{\to }n\prime =\prod _{i=1}^k{q}_i^{{\alpha }_i}$ 并且 $n\ge n^{\prime }$, 这样 $n$ 会变小.

故以下就设 $p_1,\cdots ,p_k$ 就是从小到大的最小 $k$ 个素数.

调整二

大的素因子幂应该尽可能小, 也即这里的 ${\alpha }_1\ge {\alpha }_2\ge \cdots \ge {\alpha }_k$.

调整三（有关 $2$ 的幂）

else if(isTwopower(n) && n>=8)
	{
		for(int i=1;i<=100;i++)
		{
			divisor[i]--;
		}
		ans*=8;
		int p=3;
		for(int i=3;i<=100;i++)
		{
			while(!isPrime(p))
				p++;
			if(isPrime(p))
			{
				if ((divisor[i])==0)
					break;
				else
				{
					ans*=power(p,divisor[i]);
				}

			}
			p++;
		}
	}

于是完整代码如下:

#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;
int divisor[101] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };


bool isPrime(int p)
{
	if (p == 0 || p == 1)
		return false;
	else
	{
		for (int i = 2; i < p; i++)
		{
			if (p % i == 0)
				return false;
		}
		return true;
	}

}

bool isTwopower(int n)
{
	if(n==2)
		return true;
	else
	{
		if(n%2!=0)
			return false;
		else
		{
			return isTwopower(n/2);
		}
	}
}

long long power(int p, int a)
{
	if(a==1)
		return p;
	else
	{
		return power(p,a-1)*p;
	}
}

int cur=1;

void div(int n)
{
    if(n==1)
		divisor[cur]=1;
	else
	{
		for(int i=n;i>=2;i--)
        {
            if(isPrime(i) && n%i==0)
            {
                divisor[cur]=i;
                cur++;
                div(n/i);
				break;
            }
        }
	}

}


int main()
{
	long long n,ans=1;
	cin >> n;
    div(n);


	if(n==1)
		ans=1;

	else if(isTwopower(n) && n>=8)
	{
		for(int i=1;i<=100;i++)
		{
			divisor[i]--;
		}
		ans*=8;
		int p=3;
		for(int i=3;i<=100;i++)
		{
			while(!isPrime(p))
				p++;
			if(isPrime(p))
			{
				if ((divisor[i])==0)
					break;
				else
				{
					ans*=power(p,divisor[i]);
				}

			}
			p++;
		}
	}
	else
	{
		for(int i=1;i<=100;i++)
		{
			divisor[i]--;
		}
		int p=2;
		for(int i=1;i<=100;i++)
		{
			while(!isPrime(p))
				p++;
			if(isPrime(p))
			{
				if ((divisor[i])==0)
					break;
				else
				{
					ans*=power(p,divisor[i]);
				}

			}
			p++;
		}
	}
	cout<<ans;

	return 0;
}

第二题

这题难度不大, 正常递归算法就能解决. （每次向下递归到 $n\to \frac{n}{p}$, 其中 $p$ 为 $n$ 的最小素因子）

注：之所以找最小素因子而不是最大真因子是因为通常情况下, 这样枚举的个数会大大减小，且减少了大数的运算.

import math

def is_prime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return False
    return True

def get_ans(n):
    if n==1:
        return 1
    else:
        for i in range(2,n+1):
            if n%i==0:
                return int(int(get_ans(n//i))+1)
            else:
                continue
            
n = int(input())
print(get_ans(n))

第三题

同样是采取递归的手法: 只需考虑末位为 $0$ 或首位为 $1$ 的递归即可. （这里最好把元音与辅音区分为 $1,0$ 方便一些）

import string

def get_ans(ls):
    if len(ls)==1:
        return 1
    else:
        ret = 0
        if ls[len(ls)-1]==0:
            ret = ret + get_ans(ls[0:len(ls)-1])
        if ls[0]==1:
            ls.reverse()
            ret = ret+get_ans(ls[0:len(ls)-1])
        return ret

vowels = ['a','e','i','o','u']
alphabets = input()
eqnum = []
for i in range(len(alphabets)):
    if alphabets[i] in vowels:
        eqnum.append(1)
    else:
        eqnum.append(0)
print(get_ans(eqnum))

第四题

等比数列求和. 为了简化计算, 只需注意到 $$\lfloor x\rfloor +\lfloor \frac{x}{k}\rfloor +\lfloor \frac{x}{k^2}\rfloor +\cdots \le \sum _{i=0}^{+\infty }\frac{x}{k^i}=x\cdot \frac{1}{1-\frac{1}{k}}=\frac{kx}{k-1}$$ 以及
$$\lfloor x\rfloor +\lfloor \frac{x}{k}\rfloor +\lfloor \frac{x}{k^2}\rfloor +\cdots \ge \lfloor x\rfloor +\lfloor \frac{x}{k}\rfloor$$

import sys
sys.setrecursionlimit(20000)

def get_ans(n,k):
    if n==0:
        return 0
    else:
        return (n+int(get_ans(n//k,k)))
    
n,k = map(int,input().split(' '))
res=0
if n==1:
    res = 1
else:
    low = int(n*(k-1)/k)-1
    up = int(n*(k)/(k-1))+1 
    for i in range(low,up):
        if get_ans(i,k)>=n:
            res=i
            break
        
print(res)

最终结果：$25+25+25+25=100,\text{rank}=3$

建议（部分同上次）

1. 本次比赛的编辑器并不是非常友好，例如调试中注释的快捷键 Ctrl + / 就无法使用，因此笔者在考试时实际使用了 jupyter notebook 编辑器并复制进去（20 次的复制和切屏限制应该还算合理）
2. 最后希望官方能够在比赛结束后迅速给出题解，以供学习，这样才能完全达到比赛的最好效果。
3. 比赛一开始系统就承受不住压力，等了将近两个小时才进去。希望下次能够尽量避免这种技术问题。

当然，也希望以后 CSDN 的编程竞赛能够越办越好！

欢迎关注我的博客！

我的 GitHub 账号: 欢迎 Fork + PR!

我的洛谷账号：这是我

我的洛谷团队：这是我的团队

欢迎大家关注我，在项目上与我协作哦！