Codeforces Round #382 Div. 2【数论】

程序员伟昌技术 2022年11月13日

0 收藏 862 点赞 2,458 浏览 1038 个字

C. Tennis Championship（递推，斐波那契）

题意：n个人比赛，淘汰制，要求进行比赛双方的胜场数之差小于等于1.问冠军最多能打多少场比赛。
题解：
因为n太大，感觉是个构造。写写小数据，看看有没有结论。

2 3 4 5 6 7 8 9 10 11 12 (人数)
1 2 2 3 3 3 4 4 4 4 4 (比赛数）

发现比赛数的增长成斐波那契。维护一个前缀和即可。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll dp[100];
int main()
{
    ll n;
    memset(dp,0,sizeof(dp));
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<=95;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    for(int i=1;i<=95;i++)
    {
        dp[i]=dp[i-1]+dp[i];
    }
    cin>>n;
        n--;
        for(int i=1;i<=95;i++)
        {
            if(dp[i]>=n)
            {
                printf("%d\n",i);
                break;
            }
        }
    }

D. Taxes（数论知识)

题意：你有值为n的财富，你需要交税，缴税方式有两种，一是直接交n的最大因子（除自身）二是将n拆成若干份>=2的部分，交他们的最大因子和。问缴税的最小值。
题解：
两个定理。三素数定理：大于2的奇数都可以拆成三个素数和的形式
哥德巴赫猜想：任一大于2的偶数都可写成两个质数之和。
然后，判断一下，有一个cha点，如果n是奇数，n-2是素数，答案为2. 大素数判定小心re。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int pan(ll p)
{
    for(int i=2;i<=sqrt(p);i++)
    {
        if(p%i==0) return 0;
    }
    return 1;
}
long long n;
int main()
{
    scanf("%I64d",&n);
    if(pan(n))
    {
        cout<<1<<endl;
        return 0;
    }
    if(n==2)
    {
        cout<<1<<endl;
        return 0;
    }
    if(n%2)
    {
        if(pan(n-2))
            cout<<2<<endl;
        else
            cout<<3<<endl;
    }
    else
    {
        cout<<2<<endl;
        return 0;
    }
}