poj 1845(等比数列前n项和及高速幂)

poj 1845(等比数列前n项和及高速幂)

大家好,又见面了,我是全栈君。

Sumdiv
Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 13959   Accepted: 3433

Description

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

2 3

Sample Output

15

Hint

2^3 = 8. 

The natural divisors of 8 are: 1,2,4,8. Their sum is 15. 

15 modulo 9901 is 15 (that should be output). 

Source

Romania OI 2002

思路看:

http://hi.baidu.com/necsinmyway/item/9f10b6d96c5068fbb2f77740

AC代码:

#include<iostream>using namespace std;#define LL long longLL pow_mod(LL a,LL n,int mod){         //高速幂    LL r=1;    LL base=a;    while(n){        if(n&1)            r=r*base%mod;        base=base*base%mod;        n>>=1;    }    return r%9901;}LL sum(LL a,LL b,LL mod){             //二分求等比数列前N项和    if(b==0)        return 1;    if(b%2==1)        return (sum(a,b/2,mod)*(pow_mod(a,b/2+1,mod)+1))%mod;    else        return (sum(a,b-1,mod)+pow_mod(a,b,mod))%mod;}int main(){    LL a,b;    LL ans;    while(cin>>a>>b){        ans=1;        for(LL i=2;i*i<=a;i++){           //将a分解为质数的乘积            if(a%i==0){                LL s=0;                while(a%i==0){                    s++;                    a/=i;                }                ans=ans*sum(i%9901,b*s,9901)%9901;            }        }        if(a>=2){            ans=ans*sum(a%9901,b,9901)%9901;        }        cout<<ans<<endl;    }    return 0;}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115395.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 通俗易懂讲解均方误差 (MSE)「建议收藏」

    通俗易懂讲解均方误差 (MSE)「建议收藏」测量预测值与某些真实值匹配程度。MSE通常用作回归问题的损失函数。例如,根据其属性估算公寓的价格。这是维基百科中定义的均方误差(MSE)公式。它代表了一个非常简单的概念,但如果您刚开始使用ML,可能不太容易读懂。让我们从内而外拆开包装。MSE计算模型的预测Ŷ与真实标签Y的接近程度。您希望误差变为0。如果您预测房价,误差可能是预测价格与实际价格之间的差异。从标签中减去预测是行不通的。误差可能为负也可能为正,这是对样本求和时的问题。您可以取绝对值或误差的平方。取平方有一个特性,它惩罚更大的

  • 【第01题】A + B | 基础输入输出,开启学习C语言打卡的序章

    【第01题】A + B | 基础输入输出,开启学习C语言打卡的序章难度:★☆☆☆☆,开启学习C语言打卡的序章

  • volatile关键字作用

    volatile关键字作用一、作用简述内存可见性:保证变量的可见性:当一个被volatile关键字修饰的变量被一个线程修改的时候,其他线程可以立刻得到修改之后的结果。当一个线程向被volatile关键字修饰的变量写入数据的时候,虚拟机会强制它被值刷新到主内存中。当一个线程用到被volatile关键字修饰的值的时候,虚拟机会强制要求它从主内存中读取。 屏蔽JVM指令重排序(防止JVM编译源码生成class时使用重排序)…

  • 线性规划问题(一)

    线性规划问题(一)实验目的:通过实验,使学生了解LINGO软件的基本功能,掌握LINGO软件的求解过程,以及熟悉LINGO软件的主要菜单命令,能用LINGO软件解线性规划问题。实验要求:实验步骤要有模型建立,模型

  • PyTorch 中的数据类型 torch.utils.data.DataLoader

    PyTorch 中的数据类型 torch.utils.data.DataLoaderDataLoader是PyTorch中的一种数据类型。在PyTorch中训练模型经常要使用它,那么该数据结构长什么样子,如何生成这样的数据类型?下面就研究一下:先看看 dataloader.py脚本是怎么写的(VS中按F12跳转到该脚本) __init__(构造函数)中的几个重要的属性:1、dataset:(数据类型dataset)输入的数据类型。看名字感觉就像是数据库,…

  • git clone 指定分支和切换分支[通俗易懂]

    git clone 指定分支和切换分支[通俗易懂]gitclone指定分支:gitclone-b分支名称项目地址假设分支名称为test,则:gitclone-btest项目地址git命令查看当前分支:gitbranchgit命令切换分支:gitcheckout分支名…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号