当前位置: 首页 > news >正文

洛谷题单指南-进阶数论-P2303 [SDOI2012] Longge 的问题

原题链接:https://www.luogu.com.cn/problem/P2303

题意解读:求1~n中所有数与n的GCD之和。

解题思路:

推公式!

根据题意,1~n中与n的GCD必然是n的因数,因此可以枚举所有n的因数,看有多少个数与n的gcd等于该因数。

据此得到初始公式:

image

缩减d倍之后:

image

更进一步:

image

因此,先求出n的所有因数,然后对所有因数计算d*Φ(n/d),累加即可。

100分代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;LL n, ans;LL phi(LL x)
{LL res = x;for(LL i = 2; i <= x / i; i++){if(x % i == 0){res = res * (i - 1) / i;while(x % i == 0) x /= i;}}if(x != 1) res = res * (x - 1) / x;return res;
}int main()
{cin >> n;for(LL i = 1; i <= n / i; i++){if(n % i == 0){ans += i * phi(n / i);if(i != n / i){ans +=n / i * phi(i);}}}cout << ans;return 0;
}

 

http://www.hskmm.com/?act=detail&tid=21317

相关文章:

  • PK-2877电流互感器在高频脉冲电源模块测试中的应用方案
  • VC++ 使用OpenSSL创建RSA密钥PEM档案
  • CF1699D Almost Triple Deletions
  • QMT回测模式为什么要在副图进行
  • DSA:DeepSeek Sparse Attention
  • 荒野猎手出击!启明智显ZX7981PO:专治各种恶劣环境的5G插卡路由器
  • AWS CDK重构功能发布:安全重构基础设施即代码
  • 开发即时通社交软件APP首选系统,可定制开发,可提供源码
  • 死锁的处理策略-死锁的检测和解除
  • springboot3 mybatis 数据库操控入门与实战
  • 解决winform调用wpf窗体时原窗体缩小的问题
  • 重构 Java 系统服务!JBoltAI 框架以 AIGS 方案开启企业数智化转型
  • 本土化优势凸显:Gitee如何成为中国开发团队的效率引擎
  • Linux系统OOM终止Oracle进程
  • Filebeat写ElasticSearch故障排查思路(上) - 教程
  • 数字化转型浪潮下,CI/CD工具如何成为企业软件开发效率的加速器?
  • linux 删除服务
  • Verl实验
  • 适配 20 + 主流 AI 模型!JBoltAI 框架让 Java AI 应用兼容性拉满
  • 告别 “一刀切” 管理!MyEMS 为不同行业定制专属能源优化方案
  • Fourier Features Let Networks Learn High Frequency Functions in Low Dimensional Domains
  • 「突发奇想,灵光乍现」 - hello
  • jenkins 用户权限 管理配置
  • DirectX- DLL修复工具 免费下载!绿色单文件版!安装使用教程
  • 测试集成CI/CD的五大实践:构建高效质量保障体系
  • DirectX修复工具官方中文增强版下载!下载安装教程(附安装包),0xc000007b错误解决办法
  • 死锁的处理策略-避免死锁
  • 7、微服务中 DTO、VO、PO、BO 的设计规范 - 指南
  • Gitee崛起:中国代码托管平台的自主创新之路
  • 9-30