当前位置: 首页 > article >正文

欧拉降幂-乘积幂次

题目描述

输入描述

输入共一行,包含两个整数 n,m。

输出描述

输出共一行,表示答案。

输入输出样例

示例 1

输入

2 3

 

输出

64

解题代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll p=1e9+7;  // 定义模数 p = 10^9 + 7
ll n,m;

// 快速幂函数,计算 a^b % p
ll qmi(ll a,ll b)
{
  ll res =1;
  while(b)
  {
    if(b&1)res = res*a%p;  // 如果 b 的最低位是 1,累乘到结果中
    a=a*a%p,b>>=1;  // a 自乘,b 右移一位
  }
  return res;
}

int main()
{
  cin>>n>>m;  // 输入 n 和 m

  // 计算欧拉函数 phi(p),因为 p 是质数,phi(p) = p-1
  ll c=1e9+7,phi=c;
  for(int i=2;i<=c/i;++i)
  {
    if(c%i)continue;  // 如果 i 不是 c 的因数,跳过
    phi=phi/i*(i-1);  // 更新 phi 的值
    while(c%i==0)c/=i;  // 将 c 中的所有 i 因子去掉
  }
  if(c>1)phi=phi/c*(c-1);  // 如果 c 还有剩余的大于 1 的因数,更新 phi

  // 计算 F(m) = m! % phi
  ll b=1;
  for(int i=1;i<=m;++i)b=b*i%phi;

  // 输出 n^F(m) % p
  cout<<qmi(n,b)<<'\n';
  return 0;
}

1. 题目分析:

因此,我们需要利用数论中的欧拉定理来简化计算。


欧拉定理:


方法思路:


为什么想到这个方法?


代码实现的关键点:

2. 数学原理

 

 

 

 

 

 

 


http://www.kler.cn/a/590642.html

相关文章:

  • 深入理解 IP、子网掩码、端口号和协议
  • Spring Cloud Config - 动态配置管理与高可用治理
  • 大型语言模型(LLM):解码人工智能的“语言基因“
  • Qt中打开windows的cmd窗口并显示
  • TypeScript接口 interface 高级用法完全解析
  • 深度学习-服务器训练SparseDrive过程记录
  • 文件包含与下载漏洞
  • JavaScript 元编程革命:Proxy 如何重塑语言本质
  • LLM对齐方法作用:主要解决大型语言模型(LLMs)输出与人类价值观、需求和安全规范不一致的问题
  • 【华为OD机考真题】- 用户调度问题(Java)
  • 使用zenodo-upload进行zenodo大文件上传
  • 【力扣】2666. 只允许一次函数调用——认识高阶函数
  • CellOracle|基因扰动研究基因功能|基因调控网络+虚拟干预
  • 大模型推理:LM Studio在Mac上部署Deepseek-R1模型
  • Windows安卓子系统WSA安装面具Root
  • LabVIEW旋转设备状态在线监测系统
  • 域渗透—哈希传递攻击(PTH)学习
  • 攻克 PDF 发票打印难题,提升财务效率
  • 开发者部署工具PasteSpiderV5版本更新杂谈
  • AI幻觉时代:避坑指南与技术反思