Light OJ 1054 Efficient Pseudo Code 求n^m的约数和

2024-06-15 11:48

本文主要是介绍Light OJ 1054 Efficient Pseudo Code 求n^m的约数和,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目来源:Light OJ 1054 Efficient Pseudo Code

题意:求n的m次这个数的所有的约数和

思路:首先对于一个数n = p1^a1*p2^a2*p3^a3*…*pk^ak  约束和s = (p1^0+p1^1+p1^2+…p1^a1)(p2^0+p2^1+p2^2+…p2^a2)…(pk^0+pk^1+pk^2+…pk^ak)

然后就是先求素数表 分解因子 然后求p1^0+p1^1+p1^2+…p1^a1 这是一个以1开始的等比数列 就是(1-q^n)/(1-q) 最高次用快速幂求 此外有除法 除以(1-q)乘以(1-q)的逆元

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
const long long mod = 1000000007;
const int maxn = 1000010;
//筛素数 
int vis[maxn];
LL prime[maxn];LL pow_mod(LL a, LL p)
{LL ans = 1;while(p){if(p&1){ans *= a;ans %= mod;}a *= a;a %= mod;p >>= 1;}return ans;
}void sieve(int n)
{int m = sqrt(n+0.5);memset(vis, 0, sizeof(vis));vis[0] = vis[1] = 1;for(int i = 2; i <= m; i++)if(!vis[i])for(int j = i*i; j <= n; j += i)vis[j] = 1;
}int get_primes(int n)
{sieve(n);int c = 0;for(int i = 2; i <= n; i++)if(!vis[i])prime[c++] = i;return c;
}
int main()
{int c = get_primes(100000);int cas = 1;int T;scanf("%d", &T);while(T--){LL n, m, ans = 1;scanf("%lld %lld", &n, &m);for(int i = 0; i < c && prime[i]*prime[i] <= n; i++){if(n%prime[i] == 0){int sum = 0;while(n%prime[i] == 0){sum++;n /= prime[i];}ans *= pow_mod(prime[i], sum*m+1)-1;ans %= mod;ans *= pow_mod(prime[i]-1, mod-2);ans %= mod;//ans = (ans+mod)%mod;}}if(n > 1){ans *= pow_mod(n%mod, m+1)-1;ans %= mod;ans *= pow_mod((n-1)%mod, mod-2);ans %= mod;ans = (ans+mod)%mod;//此句不加会错 原因不明 求告知 }printf("Case %d: %lld\n", cas++, ans);}return 0;
}


 

这篇关于Light OJ 1054 Efficient Pseudo Code 求n^m的约数和的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1063369

相关文章

Debugging Lua Project created in Cocos Code IDE creates “Waiting for debugger to connect” in Win-7

转自 I Installed Cocos Code IDE and created a new Lua Project. When Debugging the Project(F11) the game window pops up and gives me the message waiting for debugger to connect and then freezes. Also a

LLVM入门2:如何基于自己的代码生成IR-LLVM IR code generation实例介绍

概述 本节将通过一个简单的例子来介绍如何生成llvm IR,以Kaleidoscope IR中的例子为例,我们基于LLVM接口构建一个简单的编译器,实现简单的语句解析并转化为LLVM IR,生成对应的LLVM IR部分,代码如下,文件名为toy.cpp,先给出代码,后面会详细介绍每一步分代码: #include "llvm/ADT/APFloat.h"#include "llvm/ADT/S

VS Code 调试go程序的相关配置说明

用 VS code 调试Go程序需要在.vscode/launch.json文件中增加如下配置:  // launch.json{// Use IntelliSense to learn about possible attributes.// Hover to view descriptions of existing attributes.// For more information,

[论文笔记]QLoRA: Efficient Finetuning of Quantized LLMs

引言 今天带来LoRA的量化版论文笔记——QLoRA: Efficient Finetuning of Quantized LLMs 为了简单,下文中以翻译的口吻记录,比如替换"作者"为"我们"。 我们提出了QLoRA,一种高效的微调方法,它在减少内存使用的同时,能够在单个48GB GPU上对65B参数的模型进行微调,同时保持16位微调任务的完整性能。QLoRA通过一个冻结的4位量化预

code: 400, msg: Required request body is missing 错误解决

引起这个错误的原因是,请求参数按照get方式给。 应该给json字符串才对 补充: 1. @RequestBody String resource 加@RequestBody必须给json字符串,否则会报错400,记如标题错误。 不加这个的进行请求的话,其实post和get就没有什么区别了。 2. List<String> indexCodes=(List<String>)json.

iOS项目发布提交出现invalid code signing entitlements错误。

1、进入开发者账号,选择App IDs,找到自己项目对应的AppId,点击进去编辑, 2、看下错误提示出现  --Specifically, value "CVYZ6723728.*" for key "com.apple.developer.ubiquity-container-identifiers" in XX is not supported.-- 这样的错误提示 将ubiquity

哈理工OJ 2179(深搜)

组合 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 7(5 users)Total Accepted: 6(5 users)Rating: Special Judge: No Description 给出一个正整数N,从集合{1,2,3..N} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

解决服务器VS Code中Jupyter突然崩溃的问题

问题 本来在服务器Anaconda的Python环境里装其他的包,装完了想在Jupyter里写代码验证一下有没有装好,一运行发现Jupyter崩溃了!?报错如下所示 Failed to start the Kernel. ImportError: /home/hujh/anaconda3/envs/mia/lib/python3.12/lib-dynload/_sqlite3.cpython-

Behind the Code:与 Rakic 和 Todorovic 对话 OriginTrail 如何实现 AI 去中心化

原文:https://www.youtube.com/watch?v=ZMuLyLCtE3s&list=PLtyd7v_I7PGnko80O0LCwQQsvhwAMu9cv&index=12 作者:The Kusamarian 编译:OneBlock+ 随着人工智能技术的飞速发展,一系列前所未有的挑战随之而来:模型的衰退与互联网的潜在威胁愈发明显。AI 的增长曲线可能因训练过程中的瓶颈而趋于平