技术标签: 数论 Thinking More POJ 逆元
题目链接:
POJ 1845 Sumdiv
题意:
给出A和B,求A^B的所有因子和对990取余后的值。0<= A, B <= 50000000.
分析:
特判A=1,A=0,B=0的情况,根据任何一个大于1的自然数若其不为素数则必可唯一的分解为有限个素数的乘积。
假设A = p1^a1 * p2^a2 * p3^a3 * ... * pn^an,其中(p1,p2,p3,...,pn均为素数,a1,a2,...,an是拆分后的指数)
,那么A^B = p1^(a1*B) * p2^(a2*B) * p3^(a3*B) * ... * pn^(an*B);.
那么所有因子和的表达式为sum = (1 + p1 + p1^2 + ... + p1^(a1*B)) * (1 + p2 + p2^2 + ... + p2^(a2*B)) *...*(1 + pn + pn^2 + pn^(an*B)).
对于sum的每一项可以二分求等比数列之和。 也可以利用等比数列求和公式,但是需要用的快速乘法。
在使用等比数列求和公式时,慎用乘法逆元。用求和公式可得:(pi^(ei + 1) - 1) / (pi - 1) % mod.
但是(pi - 1)可能是mod的倍数,这样就不能直接使用费马小定理了。因为求分母的逆元要求分母*分母^(-1)%mod=1
,但分母%mod=0
恒成立,找不出模mod下的逆元。需要特判pi % mod == 0 (直接跳过),pi % mod == 1(ans = ans * (num * B + 1) % mod)
.然后用ex_gcd求逆元,还要考虑求出来的结果为负的情况,详细代码看最后一个。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const ll mod = 9901;
const int MAX_N = 10010;
int cnt;
ll A, B;
int prime[MAX_N], vis[MAX_N];
void GetPrime()
{
cnt = 0;
memset(vis, 0, sizeof(vis));
for(int i = 2; i < MAX_N; i++){
if(vis[i] == 0){
prime[cnt++] = i;
for(int j = i * i; j < MAX_N; j += i){
vis[j] = 1;
}
}
}
}
ll quick_pow(ll n, ll m)
{
ll res = 1, tmp = n % mod;
while(m){
if(m & 1) {
res = res * tmp % mod;
m--;
}
tmp = tmp * tmp % mod;
m >>= 1;
}
return res;
}
ll sum(ll a, ll n) //计算a^0 + a^1 + a^2 + ... + a^n
{
//n分奇偶考虑,例如n = 3 和n = 4的情况。
if(n == 0) return 1;
ll ans = 1, r, base, extra;
base = sum(a, (n - 1) / 2);
r = quick_pow(a, n / 2 + 1);
ans = (base + base * r % mod) % mod;
if(n % 2 == 0){
ans = (ans + quick_pow(a, n / 2)) % mod;
}
//printf("a = %lld n = %lld base = %lld r = %lld\n", a, n, base, r);
return ans;
}
void solve()
{
ll ans = 1;
for(int i = 0; prime[i] * prime[i] <= A; i++){
if(A % prime[i] == 0){
int num = 0;
while(A % prime[i] == 0){
num ++;
A /= prime[i];
}
//printf("prime[i] = %d num = %d\n", prime[i], num);
ans = ans * sum((ll)prime[i], (ll)num * B) % mod;
}
}
if(A > 1) ans = ans * sum(A, B) % mod; //别忘了这个!最后A可能是一个特别大的素数!
printf("%lld\n", ans);
}
int main()
{
GetPrime();
while(~scanf("%lld%lld", &A, &B)){
if(A == 1 || A == 0 || B == 0) printf("1\n");
else solve();
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const ll MOD = 9901;
const int MAX_N = 10010;
ll mod, A, B;
int cnt, prime[MAX_N], vis[MAX_N];
void GetPrime()
{
cnt = 0;
memset(vis, 0, sizeof(vis));
for(int i = 2; i < MAX_N; i++){
if(vis[i] == 0){
prime[cnt++] = i;
for(int j = i * i; j < MAX_N; j += i){
vis[j] = 1;
}
}
}
}
ll mul(ll n, ll m)
{
ll res = 0, tmp = n % mod;
while(m){
if(m & 1) res = (res + tmp) % mod;
tmp = (tmp + tmp) % mod;
m >>= 1;
}
return res;
}
ll quick_pow(ll n, ll m)
{
ll res = 1, tmp = n % mod;
while(m){
if(m & 1) res = mul(res, tmp);
tmp = mul(tmp, tmp);
m >>= 1;
}
return res;
}
void solve()
{
ll ans = 1;
for(int i = 0; prime[i] * prime[i] <= A; i++){
if(A % prime[i] == 0){
int num = 0;
while(A % prime[i] == 0){
num++;
A /= prime[i];
}
mod = (prime[i] - 1) * MOD;
ans = ans * (quick_pow(prime[i], num * B + 1) + mod - 1) / (prime[i] - 1) % MOD;
}
}
if(A > 1){
mod = (A - 1) * MOD;
ans = ans * (quick_pow(A, B + 1) + mod - 1) / (A - 1) % MOD;
}
printf("%lld\n", ans);
}
int main()
{
GetPrime();
while(~scanf("%lld%lld", &A, &B)){
if(A == 1 || A == 0 || B == 0) printf("1\n");
else solve();
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#include <bitset>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const ll mod = 9901;
const int MAX_N = 500000;
ll A, B;
int prime_cnt;
int prime[MAX_N];
bitset<MAX_N> bs;
void GetPrime()
{
bs.set();
prime_cnt = 0;
for(int i = 2; i < MAX_N; i++){
if(bs[i] == 1) prime[prime_cnt++] = i;
for(int j = 0; j < prime_cnt && i * prime[j] < MAX_N; j++){
bs[i * prime[j]] = 0;
if(i % prime[j] == 0) break;
}
}
//printf("bs[9901] = %d\n", (int)bs[9901]);
}
ll mul(ll a, ll b, ll m)
{
ll res = 0, tmp = a % m;
b %= m;
while(b){
if(b & 1) res = (res + tmp) % m;
tmp = (tmp + tmp) % m;
b >>= 1;
}
return res;
}
ll quick_pow(ll a, ll b, ll m)
{
ll res = 1, tmp = a % m;
while(b){
if(b & 1) res = mul(res, tmp, m);
tmp = mul(tmp, tmp, m);
b >>= 1;
}
return res;
}
ll ex_gcd(ll a, ll b, ll& x, ll& y)
{
if(b == 0) {
x = 1, y = 0;
return a;
}
ll d = ex_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
void solve()
{
ll x = A, ans = 1;
for(int i = 0; i < prime_cnt && prime[i] * prime[i] <= x; i++){
if(x % prime[i] == 0){
int num = 0;
while(x % prime[i] == 0){
num++;
x /= prime[i];
}
if(prime[i] % mod == 0) continue;
else if(prime[i] % mod == 1){
ans = ans * (num * B + 1) % mod;
continue;
}
ans = ans * (quick_pow(prime[i], num * B + 1, mod) + mod - 1) % mod;
ll xx, y;
ex_gcd((ll)prime[i] - 1, mod, xx, y);
xx = (xx % mod + mod) % mod;
ans = ans * xx % mod;
}
}
if(x > 1){
if(x % mod == 0) {
printf("%lld\n", ans);
return;
}
else if(x % mod == 1) {
ans = ans * (B + 1) % mod;
printf("%lld\n", ans);
return;
}
ans = ans * (quick_pow(x, B + 1, mod) + mod - 1) % mod;
ll xx , y;
ex_gcd(x - 1, mod, xx, y);
xx = (xx % mod + mod) % mod;
ans = ans * xx % mod;
}
printf("%lld\n", ans);
}
int main()
{
GetPrime();
while(~scanf("%lld%lld", &A, &B)){
if(A == 0 || A == 1) printf("%lld\n", A);
else if(B == 0) printf("1\n");
else solve();
}
return 0;
}
文章浏览阅读529次。百分百题库提供建筑八大员(材料员)考试试题、建筑八大员(材料员)考试预测题、建筑八大员(材料员)考试真题、建筑八大员(材料员)证考试题库等,提供在线做题刷题,在线模拟考试,助你考试轻松过关。310项目经理部应编制机械设备使用计划并报()审批。A监理单位B企业C建设单位D租赁单位答案:B311对技术开发、新技术和新工艺应用等情况进行的分析和评价属于()。A人力资源管理考核B材料管理考核C机械设备管理考核D技术管理考核答案:D312建筑垃圾和渣土._料账的试题
文章浏览阅读614次。本文由chatgpt生成,文章没有在chatgpt生成的基础上进行任何的修改。以上只是chatgpt能力的冰山一角。作为通用的Aigc大模型,只是展现它原本的实力。对于颠覆工作方式的ChatGPT,应该选择拥抱而不是抗拒,未来属于“会用”AI的人。AI职场汇报智能办公文案写作效率提升教程 专注于AI+职场+办公方向。下图是课程的整体大纲下图是AI职场汇报智能办公文案写作效率提升教程中用到的ai工具。_python自动打开浏览器
文章浏览阅读545次。Linux中安装JDK-RPM方式_linux 安装jdk rpm
文章浏览阅读25次。免费领取项目源码,请关注赞收藏并私信博主,谢谢-高校志愿者管理系统主要功能模块包括页、个人资料(个人信息。修改密码)、公共管理(轮播图、系统公告)、用户管理(管理员、志愿用户)、信息管理(志愿资讯、资讯分类)、活动分类、志愿活动、报名信息、活动心得、留言反馈,采取面对对象的开发模式进行软件的开发和硬体的架设,能很好的满足实际使用的需求,完善了对应的软体架设以及程序编码的工作,采取SQL Server 作为后台数据的主要存储单元,采用Asp.Net技术进行业务系统的编码及其开发,实现了本系统的全部功能。
文章浏览阅读122次。原标题:小米OV对于是否采用鸿蒙保持沉默,原因是中国制造需要它们目前华为已开始对鸿蒙系统大规模宣传,不过中国手机四强中的另外三家小米、OPPO、vivo对于是否采用鸿蒙系统保持沉默,甚至OPPO还因此而闹出了一些风波,对此柏铭科技认为这是因为中国制造当下需要小米OV几家继续将手机出口至海外市场。 2020年中国制造支持中国经济渡过了艰难的一年,这一年中国进出口贸易额保持稳步增长的势头,成为全球唯一..._小米宣布用鸿蒙系统
文章浏览阅读1.3k次。1.Kafka Eagle实现kafka消息监控的代码细节是什么?2.Kafka owner的组成规则是什么?3.怎样使用SQL进行kafka数据预览?4.Kafka Eagle是否支持多集群监控?1.概述在《Kafka 消息监控 - Kafka Eagle》一文中,简单的介绍了 Kafka Eagle这款监控工具的作用,截图预览,以及使用详情。今天_kafka eagle git
文章浏览阅读1.1k次,点赞29次,收藏19次。Eva.js 是一个专注于开发互动游戏项目的前端游戏引擎。:Eva.js 提供开箱即用的游戏组件供开发人员立即使用。是的,它简单而优雅!:Eva.js 由高效的运行时和渲染管道 (Pixi.JS) 提供支持,这使得释放设备的全部潜力成为可能。:得益于 ECS(实体-组件-系统)架构,你可以通过高度可定制的 API 扩展您的需求。唯一的限制是你的想象力!_eva.js
文章浏览阅读1k次。Objective-C概述Objective-C是一种面向对象的计算机语言,1980年代初布莱德.考斯特在其公司Stepstone发明Objective-C,该语言是基于SmallTalk-80。1988年NeXT公司发布了OC,他的开发环境和类库叫NEXTSTEP, 1994年NExt与Sun公司发布了标准的NEXTSTEP系统,取名openStep。1996_objective-c特点及应用领域
文章浏览阅读955次,点赞20次,收藏16次。TIM(Timer)定时器定时器可以对输入的时钟进行计数,并在计数值达到设定值时触发中断16位计数器、预分频器、自动重装寄存器的时基单元,在 72MHz 计数时钟下可以实现最大 59.65s 的定时,59.65s65536×65536×172MHz59.65s65536×65536×721MHz不仅具备基本的定时中断功能,而且还包含内外时钟源选择、输入捕获、输出比较、编码器接口、主从触发模式等多种功能。_stm32 tim寄存器详解
文章浏览阅读1.5k次。对于任何有兴趣学习前端 Web 开发的人来说,了解 HTML、CSS 和JavaScript 之间的区别至关重要。这三种前端语言都是您访问过的每个网站的用户界面构建块。而且,虽然每种语言都有不同的功能重点,但它们都可以共同创建令人兴奋的交互式网站,让用户保持参与。因此,您会发现学习所有三种语言都很重要。如果您有兴趣从事前端开发工作,可以通过多种方式学习这些语言——在艾编程就可以参与到学习当中来。在本文中,我们将回顾每种语言的特征、它们如何协同工作以及您可以在哪里学习它们。HTML vs C._艾编程学习资料
文章浏览阅读2.8k次。点云配准主要针对点云的:不完整、旋转错位、平移错位。因此要得到完整点云就需要对局部点云进行配准。为了得到被测物体的完整数据模型,需要确定一个合适的坐标系变换,将从各个视角得到的点集合并到一个统一的坐标系下形成一个完整的数据点云,然后就可以方便地进行可视化,这就是点云数据的配准。点云配准技术通过计算机技术和统计学规律,通过计算机计算两个点云之间的错位,也就是把在不同的坐标系下的得到的点云进行坐标变..._局部点云与全局点云配准
文章浏览阅读273次。提取码:0oorGoogle和YouTube由于Python的高可适应性、易于维护以及适合于快速开发而采用它。如果你想要编写高质量、高效的并且易于与其他语言和工具集成的代码,《Python学习手册:第4 版》将帮助你使用Python快速实现这一点,不管你是编程新手还是Python初学者。本书是易于掌握和自学的教程,根据作者Python专家Mark Lutz的著名培训课程编写而成。《Python学习..._零基础学pythonpdf电子书