D、E、F

数学

D - Send a Table

题意：

• 输入一个数$n$，求$1$~$n$之间与每个数互质的数总共有多少个。

解题思路：

• 如果对欧拉函数的概念了解的很透彻的话，这道题就很简单，就是求$1$~$n$的欧拉函数的前缀和，注意一下（2,3）、（3,2）算作两个答案就行了，最后答案就是2*$1$到$n$的欧拉函数前缀和-1（(1,1)只用算一次））

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5e4+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int phi[N];
int p[N];
int vis[N];
int sum[N];
void init(int n)
{
    phi[1]=1;
    memset(vis, 0, sizeof(vis));
    int cnt=0;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            p[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<cnt&&i*p[j]<= n;j++)
        {
            vis[i*p[j]]=1;
            if(i%p[j]==0)
            {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            else
            {
                phi[i*p[j]]=phi[i]*(p[j]-1);
            }
        }
    }
    sum[1]=phi[1];
    for(int i=2;i<=N;i++)
        sum[i]=sum[i-1]+phi[i];
}
int main()
{
    int n;
    init(N);
    while(scanf("%d",&n))
    {
        if(n==0)
            break;
        printf("%d\n",2*sum[n]-1);
    }
    return 0;
}

E - Huge Mods

题意：

• 计算$a1$^($a2$^($a3$^($a4$^( $a5$^(...) ) ) ) ) % $m$的值，输入$a$数组和$m$，不保证$m$是质数，不保证互质。

解题思路：

• 如果对欧拉降幂很熟悉的话这个就是个板子题，而且好像还不用判$b$>=phi(p)。直接套板子就完事儿。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=5e4+5;
const double eps=1e-4;
typedef long long ll;
typedef pair<int,ll> pil;
int phi[N];
int p[N];
int vis[N];
int sum[N];
ll get_phi(ll n)
{
    int pp=n;
    for(int i=2;i*i<=n;i++)
    {
        if(n%i!=0)
            continue;
        pp=pp/i*(i-1);
        while(n%i==0)
            n/=i;
    }
    if(n>1)
    {
        pp=pp/n*(n-1);
    }
    return pp;
}
ll Mod(ll a,ll b)
{
    return a<b?a:a%b+b;
}
ll pow_mod(ll a,ll b,ll p)
{
    ll res=1;
    while(b)
    {
        if(b&1)
            res=Mod(res*a,p);
        a=Mod(a*a,p);
        b>>=1;
    }
    return res;
}
int a[N];
int n,mod;
ll dfs(int x,int p)
{
    if(x==n)
        return Mod(a[x],p);
    int fp=get_phi(p);
    return pow_mod(a[x],dfs(x+1,fp),p);
}
char s[N];
int main()
{
    int tot=1;
    while(scanf("%s",s))
    {
        if(s[0]=='#')
            break;
        mod=atoi(s);//将s转化成int类型的
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        printf("Case #%d: ",tot++);
        printf("%lld\n",dfs(1,mod)%mod);
    }
    return 0;
}

F - Problem Makes Problem

题意：

• 将m个球放入n个盒子中，问有多少种情况。

解题思路：

• 利用中学的组合数学便可以解决——隔板法，答案就为$C(N+M-1, N-1)$。

代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<stdio.h>
#include<cstdlib>
#include<cstdio>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int N=2e6+5;
const double eps=1e-4;
const ll mod=1e9+7;
typedef pair<int,ll> pil;
ll c[N];
char s[N];
void init()
{
    c[0]=1;
    for(int i=1;i<N;i++)
        c[i]=c[i-1]*i%mod;
}
ll pow_mod(ll a,ll n)
{
    ll res=1;
    while(n)
    {
        if(n&1)
            res=res*a%mod;
        a=a*a%mod;
        n>>=1;
    }
    return res;
}
ll comb(ll n,ll m)
{
    if(n<m)
        return 0;
    return c[n]*pow_mod(c[m]*c[n-m]%mod,mod-2)%mod;//也可以预处理逆元得出组合数。
}
int main()
{
    int tot=1;
    int t;
    init();
    scanf("%d",&t);
    while(t--)
    {
        ll n,k;
        scanf("%lld%lld",&n,&k);
        printf("Case %d: ",tot++);
        printf("%lld\n",comb(n+k-1,k-1));
    }
    return 0;
}