G - Happy 2004------(HDU 1452)

简介:

传送门

Happy 2004

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1346    Accepted Submission(s): 977


Problem Description
Consider a positive integer X,and let S be the sum of all positive integer divisors of 2004^X. Your job is to determine S modulo 29 (the rest of the division of S by 29).

Take X = 1 for an example. The positive integer divisors of 2004^1 are 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 and 2004. Therefore S = 4704 and S modulo 29 is equal to 6.
 

Input
The input consists of several test cases. Each test case contains a line with the integer X (1 <= X <= 10000000).

A test case of X = 0 indicates the end of input, and should not be processed.
 

Output
For each test case, in a separate line, please output the result of S modulo 29.
 

Sample Input
 
 
1 10000 0
 

Sample Output
 
 
6 10
 

题目大意:
求 2004^X的所有因子的和 模上29的值;

解题思路:

首先根据算术基本定理(1),
若 n 的标准素因子分解表达式为 n = p1^e1 * p2^e2 * …… * pk^ek
设f(n) 为n 的所有因子之和,则有:
f(n) = (p1^(e1+1)-1)/(p1-1) * (p2^(e2+1)-1)/(p2-1) * ... * (pk^(ek+1)-1)/(pk-1)
因为2004 = 2^2 * 3 * 167,所以2004^x也肯定是2^(2*x) * 3^x * 167^x;
然后根据算术基本定理:
167 Mod 29 == 22 所以直接用22就行
((2^(2*x+1)-1)/(2-1) * (3^(x+1)-1)/(3-1) *  (22^(x+1)-1)/(22-1)) Mod 29 
设a = (2^(2*x+1)-1)/1;
设b = (3^(x+1)-1)/2 ;
设c = (22^(x+1)-1)/21);
我们只要分别求出 a Mod 29, b Mod 29, c Mod 29的值就行啦,因为他们带着除数所以 我们进行求解逆元,分别是
1Mod29的逆元 2Mod29的逆元 21Mod29的逆元,这个可以根据扩展欧几里得算法得到,求出之后,我们就进行快速幂 分别求出2^(2x+1)Mod 29 , 3^(x+1)Mod 29,  22^(x+1)Mod 29 的值,然后减一 与 前面所求的逆元进行相乘就ok了
最后输出的就是 a*b*c Mod 29,下面是详细代码:

#include <iostream>

using namespace std;
typedef long long LL;
LL quick_mod(LL a, LL b, LL m)
{
    LL ans = 1;
    while(b)
    {
        if(b & 1)
            ans = (ans*a)%m;
        b>>=1;
        a = (a*a)%m;
    }
    return ans;
}
void exgcd(LL a, LL b, LL &x, LL &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return;
    }
    LL x1, y1;
    exgcd(b, a%b, x1, y1);
    x = y1;
    y = x1 - (a/b)*y1;
}
int main()
{
    LL n, a, b, c, y, _a, _b, _c;
    while(cin>>n,n)
    {
        exgcd(1,29,_a,y);
        exgcd(2,29,_b,y);
        exgcd(21,29,_c,y);
        _a = (_a+29)%29;
        _b = (_b+29)%29;
        _c = (_c+29)%29;
        ///cout<<167%29<<endl;
        ///cout<<_a<<" "<<_b<<" "<<_c<<endl;
        a=(quick_mod(2,2*n+1,29)-1)*_a;
        b=(quick_mod(3,n+1,29)-1)*_b;
        c=(quick_mod(22,n+1,29)-1)*_c;
        cout<<(a*b*c%29)<<endl;
    }
    return 0;
}


目录
相关文章
大学物理(上)-期末知识点结合习题复习(1)——运动的描述(两类运动学知识点、圆周运动知识点、相对运动知识点)
大学物理(上)-期末知识点结合习题复习(1)——运动的描述(两类运动学知识点、圆周运动知识点、相对运动知识点)
465 0
|
负载均衡 监控 Java
Spring Cloud Gateway 全解析:路由配置、断言规则与过滤器实战指南
本文详细介绍了 Spring Cloud Gateway 的核心功能与实践配置。首先讲解了网关模块的创建流程,包括依赖引入(gateway、nacos 服务发现、负载均衡)、端口与服务发现配置,以及路由规则的设置(需注意路径前缀重复与优先级 order)。接着深入解析路由断言,涵盖 After、Before、Path 等 12 种内置断言的参数、作用及配置示例,并说明了自定义断言的实现方法。随后重点阐述过滤器机制,区分路由过滤器(如 AddRequestHeader、RewritePath、RequestRateLimiter 等)与全局过滤器的作用范围与配置方式,提
Spring Cloud Gateway 全解析:路由配置、断言规则与过滤器实战指南
|
数据库
【YashanDB知识库】load data一次导入多个文件的数据时报错
简介:本文解决使用 LOAD DATA 一次导入多个文件时命令格式错误的问题。关键词为 load data 和多个文件。问题在于尝试用空格或逗号间隔文件失败。正确方法是在 INFILE 子句中单独指定每个文件并以空格分隔。此问题影响所有版本,修复方式适用于数据库当前版本。示例代码展示正确配置及多文件导入方法。
|
机器学习/深度学习 JavaScript 前端开发
深入探索WebAssembly:提升Web应用的性能
【10月更文挑战第15天】深入探索WebAssembly:提升Web应用的性能
586 3
基于SVPWM的飞轮控制系统的simulink建模与仿真
本课题基于SVPWM的飞轮控制系统的Simulink建模与仿真,利用MATLAB2022a实现。SVPWM通过在αβ坐标系中表示三相电压矢量,精确追踪圆形电压空间矢量轨迹,提高直流母线电压利用率和输出电压谐波质量,增强电机转矩密度和效率。仿真结果显示系统性能优越,能量转换效率高,谐波含量低,电机运行平稳,响应快速,适用于储能需求动态调整,显著提升飞轮储能系统的整体性能。
|
存储 关系型数据库 MySQL
《深度探秘:PaddlePaddle中利用MySQL存储模型训练数据》
本文探讨了在PaddlePaddle中利用MySQL存储模型训练数据的方法与优势。MySQL以其结构化数据管理能力、强大查询功能及数据持久化特性,为PaddlePaddle的训练数据提供高效存储方案。文章从数据库表结构设计、数据预处理到训练过程中的数据交互(如加载、记录、更新)进行了详细说明,并分析了可能遇到的数据一致性、性能和安全问题及其解决方案。通过合理规划与优化,可充分发挥两者结合的优势,提升机器学习模型训练效率与稳定性。
425 32
|
机器学习/深度学习 Web App开发 JavaScript
正则Regester
正则Regester
456 0
正则Regester
|
人工智能 Python
[oeasy]python039_for循环_循环遍历_循环变量
本文回顾了上一次的内容,介绍了小写和大写字母的序号范围,并通过 `range` 函数生成了 `for` 循环。重点讲解了 `range(start, stop)` 的使用方法,解释了为什么不会输出 `stop` 值,并通过示例展示了如何遍历小写和大写字母的序号。最后总结了 `range` 函数的结构和 `for` 循环的使用技巧。
351 4
|
Linux 存储
Linux 调用系统命令并截获标准输出(stdout)和错误输出(stderr)
<pre><b>char</b> ret[1024]; <b>char</b> *<b>DoSysCmd</b>(<b>char</b> * cmdline){ <b>FILE</b> *fp; <b>char</b> line[32]; <b>char</b> cmdtmp[256]; <b>memset</b>(cmdtmp,0x00,256);
2059 0
|
设计模式 物联网 关系型数据库
掌握命令模式-解锁软件设计的‘遥控器’
本文首先通过场景案例展示了不使用设计模式的传统实现方式,指出其存在的问题,如代码耦合度高、扩展性差等。随后,文章详细介绍了命令模式的核心结构和原理,并通过示例代码展示了如何使用命令模式重构案例,有效解决了传统实现方式中的问题。在回顾与展望部分,文章总结了命令模式的优点,如降低耦合性、提高扩展性和灵活性,同时也探讨了其可能存在的缺点,如增加系统复杂性。最后,文章还讨论了命令模式的应用场景,并对未来的发展趋势进行了展望。
341 0
掌握命令模式-解锁软件设计的‘遥控器’