约数个数和欧拉函数

简介: 约数个数和欧拉函数

约数个数

求约数个数可以先分解质因式

int整数范围内,约数最多的数最多有1600个,所以暴力搜索是没事的


1.轻拍牛头

信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)

题意就是问:全部数中除自己外有多少个因数,重复也算

则我们可以用小的因数更新大的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
int cnt[N],a[N],s[N];//cnt记录每个数的次数,s是个因数的和
int main()
{
   int n;
   scanf("%d",&n);
   for(int i=1;i<=n;i++)
   {
       scanf("%d",&a[i]);
       cnt[a[i]]++;
   }
   for(int i=1;i<N;i++)//枚举所有数
     for(int j=i;j<N;j+=i)//枚举他的倍数
         s[j]+=cnt[i];//这个数加上这个因数的个数
   for(int i=1;i<=n;i++) printf("%d\n",s[a[i]]-1);//输出答案,因为自己不算在里面则减一
    return 0;
}

2.樱花

信息学奥赛一本通(C++版)在线评测系统 (ssoier.cn)

因为x>0并且是整数,则y-n!>0并且n!^2整除y-n!,则相当于问n!^2的约数个数都对应一个y跟x,约数就整除嘛,所以直接求n!^2的不同约数个数即可



约数个数就是(2c1+1)(2c2+1)...(2ck+1)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=1e9+7;
int prime[N],cnt;
bool st[N];
void init(int n)//筛质数
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]*i<=n;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }
}
int main()
{
    int n;
    cin>>n;
    init(n);
    int res=1;
    for(int i=0;i<cnt;i++)//枚举质数
    {
        int p=prime[i];
        int s=0;
        for(int j=n;j;j/=p) s+=j/p;//求p的次方
        res=(ll)res*(2*s+1)%mod;//答案乘上个数
    }
    cout<<res<<endl;
    return 0;
}

3.反素数

198. 反素数 - AcWing题库

相当于求小于n中约数最多的数的最小数,因为不同的质数最多有9个,因为2*3*5*7*11*13*17*19*23*29>2e9,所以只需前9个不同质数即可构成所有的约数


然后2^31>2e9,所以最多枚举到30次方即可,用dfs暴搜来求

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,mod=1e9+7;
int prime[9]={2,3,5,7,11,13,17,19,23};
int maxd,number;
int n;
void dfs(int u,int last,int p,int s)//u是当前的质数,last是当前的次方,p是当前的数,s是当前的数的约数个数
{
    if(s>maxd||s==maxd&&p<number)//假如有大于当前约数的约数,或者约数数相等但是数比较小的更新一下
    {
        maxd=s;
        number=p;
    }
    if(u==9) return;//假如枚举完所有质数
    for(int i=1;i<=last;i++)//枚举所有次方
    {
        if((ll)p*prime[u]>n) break;//假如大于n则不用操作了,直接跳出
        p*=prime[u];//更新一下p
        dfs(u+1,i,p,s*(i+1));//递归下一个的质数,求约数的公式(约数变成了s*(i+1))
    }
}
int main()
{
    cin>>n;
    dfs(0,30,1,1);//暴搜来求约数最多的数的最小数
    cout<<number<<endl;
    return 0;
}


4.Hankson的趣味题

200. Hankson的趣味题 - AcWing题库

因为d是[x,c]的最小公倍数,所以枚举所有d的约数来判断符不符合[x,a]的最大公约数是b,[x,c]的最小公倍数是d,假如满足就res++;


枚举约数的个数可以先分解质因数,在dfs暴搜求每个约数即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int prime[N],cnt;
bool st[N];
int a,b,c,d;
int fcnt;
struct
{
    int p,s;
}f[1601];//存质因数跟次幂
int divide[1601],dcnt;//存约数
int gcd(int a,int b)//求最大公约数
{
    return b?gcd(b,a%b):a;
}
void dfs(int u,int p)//枚举到第u个 当前的约数是p
{
    if(u==fcnt)//假如枚举完了,这是个合法的约数
    {
        divide[dcnt++]=p;
        return;
    }
    for(int i=0;i<=f[u].s;i++)//枚举所有次幂
    {
        dfs(u+1,p);
        p*=f[u].p;//更新一下p
    }
}
void init(int n)//线性筛
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]*i<=n;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }
}
void solve()
{
    fcnt=dcnt=0;
    int res=0;
    cin>>a>>b>>c>>d;
    int t=d;
    //将d进行分解质因式
    for(int i=0;prime[i]<=t/prime[i];i++)//枚举所有质因子
    {
        int p=prime[i];
        if(t%p==0)
        {
            int s=0;
            while(t%p==0) t/=p,s++;
            f[fcnt++]={p,s};//记录这个质因数跟幂次
        }
    }
    if(t>1) f[fcnt++]={t,1};//假如有剩余,也存起来
    dfs(0,1);//暴力搜索所有约数
    for(int i=0;i<dcnt;i++)//枚举d的所有约数
    {
        int x=divide[i];
        if(gcd(a,x)==b&&(ll)c*x/gcd(x,c)==d) res++;//假如满足条件则答案++
    }
    cout<<res<<endl;
}
int main()
{
    init(100000);//预处理出来质数
    int T;
    cin>>T;
    while(T--) solve();
    return 0;
}

欧拉函数

欧拉函数:1~i中与i互质的数

欧拉筛模板

void init(int n)//欧拉筛
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) 
        {
            prime[cnt++]=i;
            pri[i]=i-1;
        }
        for(int j=0;prime[j]*i<=n;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0) 
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}

1.可见的点

201. 可见的点 - AcWing题库

假如[x,y]x与y不互质,则必能约成最简【x/d,y/d】所以[x,y]这个点会被[x/d,y/d]


这个点挡住,所以只要求与x互质的y的个数加起来就是答案了,因为两边互质的数关于y=x对称,则只需y=x下面的互质数在×2就为答案,因为y=x也有一条则最终的答案+1

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int prime[N],cnt;
bool st[N];
int phi[N];
void init(int n)//欧拉筛
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;prime[j]*i<=n;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    init(1010);//预处理出来欧拉函数
    int T;
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        int n,res=0;
        cin>>n;
        for(int i=1;i<=n;i++) res+=2*phi[i];//求答案
        printf("%d %d %d\n",i,n,res+1);
    }
    return 0;
}

2. 最大公约数

220. 最大公约数 - AcWing题库

gcd(a,b)=素数d,则gcd(a/d,b/d)=1,则a/d,b/d互质,枚举质数d然后加上1~n/d的欧拉数即为答案


x,y属于(1~n/d)则映射到二维坐标就跟上一题的求法一样了,就问1~n/d之间的互质数对个数,所以提前预处理出来前缀和即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e7+10;
int prime[N],cnt;
bool st[N];
int phi[N];
ll s[N];//记录欧拉函数的前缀和
void init(int n)//欧拉筛
{
    phi[1]=0;//1与0互质,但是0不算在里面,则初始化为0
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;prime[j]*i<=n;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    phi[1]=0;
    for(int i=1;i<=n;i++) s[i]=s[i-1]+phi[i];//处理出来欧拉数的前缀和
}
int main()
{
    int n;
    ll res=0;
    cin>>n;
    init(n);//欧拉筛
    for(int i=0;i<cnt;i++)//枚举所有的质数d
    {
        int d=prime[i];
        res+=s[n/d]*2+1;//答案加上n/d的互质数队,跟上一题一样
    }
    printf("%lld\n",res);
    return 0;
}
相关文章
|
开发框架 .NET 网络性能优化
MCS-51单片机的基本结构
MCS-51单片机的基本结构
2819 1
|
人工智能 供应链 监控
数字孪生与农业:精准农业的发展趋势
数字孪生技术正逐步渗透到农业生产的各个环节,通过创建物理实体的数字副本,实现对实体状态的精确模拟和预测。在农业领域,这一技术的应用正引领着精准农业的发展趋势,包括智慧栽培、环境智能控制、精准农业管理和农业供应链优化等方面,为农业生产的智能化、高效化和可持续发展提供了强大的技术支持。
|
7月前
|
人工智能 安全 Serverless
人人都在造 Skill,谁来保障安全运行?
函数计算AgentRun全新升级:支持Skills安全私域托管、沙箱隔离与秒级加载,内置AI辅助Markdown极速创建技能;提供千种预置技能一键接入,兼顾企业级安全合规与极致性能,打造AI Agent时代可靠基础设施。
|
图形学 缓存 算法
掌握这五大绝招,让您的Unity游戏瞬间加载完毕,从此告别漫长等待,大幅提升玩家首次体验的满意度与留存率!
【8月更文挑战第31天】游戏的加载时间是影响玩家初次体验的关键因素,特别是在移动设备上。本文介绍了几种常见的Unity游戏加载优化方法,包括资源的预加载与异步加载、使用AssetBundles管理动态资源、纹理和模型优化、合理利用缓存系统以及脚本优化。通过具体示例代码展示了如何实现异步加载场景,并提出了针对不同资源的优化策略。综合运用这些技术可以显著缩短加载时间,提升玩家满意度。
2084 6
|
机器学习/深度学习 编解码 算法
超分辨率相关的开源项目
该文档介绍了多种超分辨率模型及其GitHub项目地址,包括Real-ESRGAN(优化真实图片质量)、RCAN(基于残差结构与通道注意力机制)、SwinIR(基于Swin Transformer的图像恢复)、FSRCNN(轻量级快速超分辨率)、EDSR(增强型深度残差网络)、SRGAN(利用GAN的超分辨率模型)及LapSRN(多级Laplacian金字塔超分辨率)。
|
消息中间件 应用服务中间件 网络安全
rabbitMQ镜像模式搭建
rabbitMQ镜像模式搭建
|
测试技术
软件复杂度量化:McCabe度量法及其环路复杂度的计算方法
McCabe度量法(McCabe&#39;s Cyclomatic Complexity)是一种经典的方法,用于度量软件程序的复杂度。通过计算程序中独立路径的数量,帮助开发人员评估代码的维护难度和测试覆盖率。本文详细介绍了McCabe度量法的原理、计算方法及其在实际应用中的作用。
3765 0
|
Go
Golang语言基础数据类型之字符串常用的操作
这篇文章介绍了Golang语言中字符串的定义、常用操作,包括字符串长度查看、遍历、类型转换、子串统计、比较、查找位置、替换、切割、大小写转换、剔除字符、前缀后缀判断、拼接、子串包含判断以及字符串join操作,同时提供了官方文档的查看方法。
504 1
|
存储 缓存 分布式计算
分布式系统开发实战:分布式存储,分布式存储常用技术
互联网每天产生数以亿计的数据,这些数据如何能够被正确地存储、解析、利用,是摆在每个数据公司面前的挑战。传统的关系型数据库,对于处理大规模的数据显得力不从心,由此以NoSQL为代表的分布式存储应运而生。 NoSQL,泛指非关系型的数据库。NoSQL数据库的产生旨在解决大规模数据集合多重数据种类带来的挑战,尤其是大数据应用的难题。
|
存储 NoSQL 定位技术
13)使用 Redis 查询附近的人或商家
13)使用 Redis 查询附近的人或商家
573 0