nefu 1262 五十弦翻塞外声

快速求一个数的因子和:唯一分解定理。
在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+3;
//小于1e12的最大素数 999999999989
//大于1e6的最小素数 1e6+3  注意打表素数筛的N>=1e6+3 否则会被999999999989这个数据卡掉
ll T,n,cnt,prime[N+10];
bool vis[N+10];
void get_prime()
{
    memset(vis,1,sizeof(vis));
    vis[1]=0;
    for(int i=2;i<=N;i++)
    {
        if(vis[i])prime[++cnt]=i;
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
ll f(ll x)//求x的因子和
{
    ll s=1;
    for(ll i=1;prime[i]*prime[i]<=x;i++)//找x的素因子
    {
        if(x%prime[i]==0)
        {
            ll t=1;
            while(x%prime[i]==0)
                t=t*prime[i],x=x/prime[i];
            s*=(t*prime[i]-1)/(prime[i]-1);
        }
    }
    if(x>1)s*=(1+x);//若x未被除尽到1,说明最后的x还剩下一个素数没有乘到答案里面,把它乘进去
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    get_prime();
    cin>>T;
    while(T--)
    {
        cin>>n;
        printf("%lld\n",f(n));
    }
    return 0;
}

hdu 1215 七夕节

在这里插入图片描述
题意是求一个数的因子和,再减去这个数本身。

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,x;
ll sum(ll x)//求x的因子和
{
    ll s,ans=1;
    for(int i=2;i*i<=x;i++)//x的素因子一定小于等于x,即i*i<=x
    {
        if(x%i==0)//i为x的素因子,设为p
        {
            s=1;//s记录x的素因子的乘积
            while(x%i==0)
                x=x/i,s=s*i;
            //while结束时s=p^n
            ans*=(s*i-1)/(i-1);
            //等比数列公式 1+p^1+p^2+...+p^n = (p^(n+1)-1)/(p-1) = (s*p-1)/(p-1)
            //就是代码中的(s*i-1)/(i-1)
        }
    }
    if(x>1)ans*=(1+x);//x>1说明x自身是素数,乘以(1+p)即(1+x)
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>x;
        printf("%lld\n",sum(x)-x);
    }
    return 0;
}

hdu 1286 找新朋友

在这里插入图片描述
题意是要求n的欧拉函数。可以改编一下素数筛的模板,打表欧拉函数。

AC代码:

#include <bits/stdc++.h>
using namespace std;
const int N=32800;
bool vis[N];
int t,x,cnt,phi[N],prime[N];
void get_phi()
{
    phi[1]=1;
    for(int i=2;i<N;i++)
    {
        if(vis[i]==0)
        {
            prime[++cnt]=i;
            phi[i]=i-1;//i为素数,欧拉函数值为i-1
        }
        for(int j=1;j<=cnt&&i*prime[j]<N;j++)
        {
            vis[i*prime[j]]=1;
            phi[i*prime[j]]=phi[i]*phi[prime[j]];//两个数互质,则phi(a*b)=phi(a)*phi(b)
            if(i%prime[j]==0)//prime[j](设为p)是i的素因子
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                //两个数不互质,但p是i的素因子,则phi(i*p)=phi(i)*p
                break;
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    get_phi();
    cin>>t;
    while(t--)
    {
        cin>>x;
        printf("%d\n",phi[x]);
    }
    return 0;
}

hdu 2048 神、上帝以及老天爷

错排公式的递推关系
D(1) = 0, D(2) = 1
D(n) = (n-1) [D(n-2) + D(n-1)]

推导过程如下:(转自博客https://www.cnblogs.com/lemonbiscuit/p/7776135.html
在这里插入图片描述

AC代码:

#include <bits/stdc++.h>
using namespace std;
long long t,n,s;
double d[25],ans[25];
void get_ans()
{
    d[1]=0;d[2]=1;
    ans[1]=0;ans[2]=0.5;
    s=2;
    for(int i=3;i<=20;i++)
    {
        s=s*i;
        d[i]=(i-1)*(d[i-1]+d[i-2]);
        ans[i]=(1.0*d[i])/(1.0*s);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    get_ans();
    cin>>t;
    while(t--)
    {
        cin>>n;
        printf("%.2lf%%\n",ans[n]*100);//printf打印百分号要写两个百分号
    }
    return 0;
}