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)


相关推荐

  • 常用排序算法:直接选择排序[通俗易懂]

    常用排序算法:直接选择排序[通俗易懂]常用排序算法:直接选择排序

  • LAMP架构简介与概述 及服务安装

    LAMP架构简介与概述 及服务安装1、LAMP平台概述(1)LAMP平台概述LAMP架构是目前成熟的企业网站应用模式之一,指的是协同工作的一整台系统和相关软件,能够提供动态web站点服务及其应用开发环境LAMP是一个缩写词,具体包括Linux操作系统,Apache网站服务器,MySQL数据库服务器,PHP(或perl,Python)网页编程语言(2)构建LAMP平台顺序在构建LAMP平台时,各组件的安装顺序依次为Linux,Apache,MySQL,PHP其中Apache和MySQL的安装并没有严格的顺序要求,而PH

    2022年10月16日
  • 教你如何暴力破解wifii密码

    使用kalilinux系统进行wifi暴力破解获取密码注意:私自破解他人WiFi属于违法行为,本教程仅供学习与参考。破解工具破解工具:kalilinux系统 ,本教程使用的装在物理机的linux系统(虚拟机使用方法一样)。支持监听模式的无线网卡,本教材使用的是某宝购买的3070L网卡。字典文件(如果你没有字典也没有问题后面会教你如何使用cruncl创建密码文件)。…

  • java json对象转map_java引用对象

    java json对象转map_java引用对象1.由json字符串转换成Map对象如json字符串:{“contend”:[{“bid”:“22”,“carid”:“0”},{“bid”:“22”,“carid”:“0”}],“result”:100,“total”:2}下面直接附代码://json字符串Stringjsondata=”{\”contend\”:[{\”bid\”:\”22\”,\”carid\”:\”0\”},{\”bid\”:\”22\”,\”carid\”:\”0\”}],\”result\”:100,\”total\”

  • 手机框架_移动端框架_跨平台_汇总_哪个好[通俗易懂]

    uni-app【重点推荐】是一个使用Vue.js开发跨平台应用的前端框架,开发者编写一套代码,到7个平台,Android版iOS版H5版微信小程序版支付宝小程序版百度小程序版头条小程序版https://uniapp.dcloud.io/DCloud即数字天堂(北京)网络技术有限公司是W3C成员及HTML5中国产业联盟发起单位,旗下产品:…

  • 分子模拟软件amber_容天AMBER优化的GPU解决方案

    分子模拟软件amber_容天AMBER优化的GPU解决方案AMBER认证的GPU系统AMBER认证GPU系统提供商容天更快地运行MD仿真容天与AMBER的主要开发商合作开发了交钥匙解决方案,为GPU加速的生物分子模拟提供增值系统。经过验证的系统,每个用户的CPU,GPU,内存和存储具有适当的平衡。从工作站到超级计算机的高度可扩展系统,具有3年保修和支持。容天AMBER优化的GPU加速系统更快地完成MD仿真并不需要花费很多。我们的AMBERG…

发表回复

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

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