Luogu 4139 上帝与集合的正确用法
2024-09-09 21:51:08
扩展欧拉定理:$a^{b} \equiv a^{b Mod \varphi (p) + \varphi (p)} (Mod p) $ $(b \geq \varphi (p))$ 。
这道题中$\varphi (p)$一定是一个偶数,所以余数为$0$。
这样子的话只需要递归求解就可以了,可以知道一定不会超过$log$层。
时间复杂度$O(maxN + Tlognlogn)$。
Code:
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll; const int N = 1e7 + ; int testCase, pCnt, pri[N];
ll n, phi[N];
bool np[N]; template <typename T>
inline void read(T &X) {
X = ; char ch = ; T op = ;
for(; ch > ''|| ch < ''; ch = getchar())
if(ch == '-') op = -;
for(; ch >= '' && ch <= ''; ch = getchar())
X = (X << ) + (X << ) + ch - ;
X *= op;
} void sieve() {
phi[] = 1LL;
for(int i = ; i < N; i++) {
if(!np[i]) pri[++pCnt] = i, phi[i] = i - ;
for(int j = ; j <= pCnt && i * pri[j] < N; j++) {
np[i * pri[j]] = ;
if(i % pri[j] == ) {
phi[i * pri[j]] = phi[i] * pri[j];
break;
}
phi[i * pri[j]] = phi[i] * (pri[j] - );
}
}
} inline ll pow(ll a, ll b, ll P) {
ll res = 1LL;
for(; b > ; b >>= ) {
if(b & ) res = res * a % P;
a = a * a % P;
}
return res;
} ll solve(ll now) {
if(now == ) return ;
return pow(2LL, phi[now] + solve(phi[now]), now);
} int main() {
sieve();
for(read(testCase); testCase--; ) {
read(n);
printf("%lld\n", solve(n));
}
return ;
}
最新文章
- Java 数组打印数组的 五种方法
- java常用设计模式
- JQuery 快速入门
- margin:0 auto 与 text-align:center 的区别
- 使用phpmyadmin修改XAMPP中MySQL的默认空密码
- Android SDK Manager 中如果没有相应的镜像ARM XX Image
- 查找最小的k 个元素之C#算法实现
- 【Moqui业务逻辑翻译系列】Shipment Receiver Receives Shipment with Packing Slip but no PO
- 深入浅出JSON
- php归获取当前目录下的二级目录数 和文件数
- [DHTML]什么是DHTML?
- C# DataTable的詳細使用方法
- 网站服务管理系统wdcp简介及功能特性
- 模式识别(1)——PCA算法
- H3CNE实验:配置基于端口划分的VLAN及Trunk
- Python基础--函数的嵌套和闭包
- ORM以及Django使用ORM创建表
- java 方法的重载
- Centos7.4 防火墙配置
- HDU 3308 LCIS (经典区间合并)【线段树】
热门文章
- nyoj-1099-Lan Xiang&#39;s Square(几何,水题)
- .net remoting和wcf自托管——一个bug引发的警示
- LeetCode Range Addition II
- 【LeetCode】006. ZigZag Conversion
- java 使用最新api操作mongodb
- redis 双写一致性问题
- ajax中error函数参数详解
- [转]java 中的序列化是什么意思?有什么好处?
- (转)NHibernate之Generator主键生成方式
- linux指令 apt-grt指令使用