BZOJ3884. 上帝与集合的正确用法(欧拉定理,广义欧拉降幂)

2024-04-16 01:38

本文主要是介绍BZOJ3884. 上帝与集合的正确用法(欧拉定理,广义欧拉降幂),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description
根据一些书上的记载,上帝的一次失败的创世经历是这样的:
第一天, 上帝创造了一个世界的基本元素,称做“元”。
第二天, 上帝创造了一个新的元素,称作“α”。“α”被定义为“元”构成的集合。容易发现,一共有两种不同的“α”。
第三天, 上帝又创造了一个新的元素,称作“β”。“β”被定义为“α”构成的集合。容易发现,一共有四种不同的“β”。
第四天, 上帝创造了新的元素“γ”,“γ”被定义为“β”的集合。显然,一共会有16种不同的“γ”。
如果按照这样下去,上帝创造的第四种元素将会有65536种,第五种元素将会有2^65536种。这将会是一个天文数字。
然而,上帝并没有预料到元素种类数的增长是如此的迅速。他想要让世界的元素丰富起来,因此,日复一日,年复一年,他重复地创造着新的元素……
然而不久,当上帝创造出最后一种元素“θ”时,他发现这世界的元素实在是太多了,以致于世界的容量不足,无法承受。因此在这一天,上帝毁灭了世界。
至今,上帝仍记得那次失败的创世经历,现在他想问问你,他最后一次创造的元素“θ”一共有多少种?
上帝觉得这个数字可能过于巨大而无法表示出来,因此你只需要回答这个数对p取模后的值即可。
你可以认为上帝从“α”到“θ”一共创造了109次元素,或1018次,或者干脆∞次。
一句话题意:

Input
接下来T行,每行一个正整数p,代表你需要取模的值
Output
T行,每行一个正整数,为答案对p取模后的值
Sample Input
3
2
3
6
Sample Output
0
1
4
Hint
对于100%的数据,T<=1000,p<=10^7

Source
By PoPoQQQ

思路:
欧拉定理:𝑎𝜑(𝑛) ≡ 1(𝑚𝑜𝑑 𝑛) .
降幂公式
在这里插入图片描述
因为大于2的欧拉函数值均为偶数,所以一定满足降幂公式的第三条
定义 f ( p ) f(p) f(p) 为模p时的答案,易知 f ( 1 ) = 0 f(1) = 0 f(1)=0
f ( p ) = 2 f(p) = 2 f(p)=22… (mod p) = 22…mod𝜑(𝑝)+𝜑(𝑝) = 2f(𝜑(𝑝))+𝜑(𝑝)
递归地计算 f f f函数即可。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;typedef long long ll;ll qpow(ll x,ll n,ll mod)
{ll res = 1;while(n){if(n & 1)res = (res * x) % mod;x = x * x % mod;n >>= 1;}return res;
}ll phi(ll n)
{int m = (int)sqrt(n + 0.5);ll ans = n;for(int i = 2;i <= m;i++){if(n % i == 0){ans = ans / i * (i - 1);while(n % i == 0) n /= i;}}if(n > 1)ans = ans / n * (n - 1);return ans;
}ll f(ll p)
{if(p == 1) return 0;ll Phi = phi(p);return qpow(2,f(Phi) + Phi,p);
}int main()
{int T;scanf("%d",&T);while(T--){ll p;scanf("%lld",&p);printf("%lld\n",f(p));}return 0;
}

这篇关于BZOJ3884. 上帝与集合的正确用法(欧拉定理,广义欧拉降幂)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/907485

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

MyBatis 动态 SQL 优化之标签的实战与技巧(常见用法)

《MyBatis动态SQL优化之标签的实战与技巧(常见用法)》本文通过详细的示例和实际应用场景,介绍了如何有效利用这些标签来优化MyBatis配置,提升开发效率,确保SQL的高效执行和安全性,感... 目录动态SQL详解一、动态SQL的核心概念1.1 什么是动态SQL?1.2 动态SQL的优点1.3 动态S

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

JavaScript Array.from及其相关用法详解(示例演示)

《JavaScriptArray.from及其相关用法详解(示例演示)》Array.from方法是ES6引入的一个静态方法,用于从类数组对象或可迭代对象创建一个新的数组实例,本文将详细介绍Array... 目录一、Array.from 方法概述1. 方法介绍2. 示例演示二、结合实际场景的使用1. 初始化二

一文带你了解SpringBoot中启动参数的各种用法

《一文带你了解SpringBoot中启动参数的各种用法》在使用SpringBoot开发应用时,我们通常需要根据不同的环境或特定需求调整启动参数,那么,SpringBoot提供了哪些方式来配置这些启动参... 目录一、启动参数的常见传递方式二、通过命令行参数传递启动参数三、使用 application.pro

关于@RequestParam的主要用法详解

《关于@RequestParam的主要用法详解》:本文主要介绍关于@RequestParam的主要用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 基本用法2. 默认值3. 可选参数4. 绑定到对象5. 绑定到集合或数组6. 绑定到 Map7. 处理复杂类

SQL中的CASE WHEN用法小结

《SQL中的CASEWHEN用法小结》文章详细介绍了SQL中的CASEWHEN函数及其用法,包括简单CASEWHEN和CASEWHEN条件表达式两种形式,并通过多个实际场景展示了如何使用CASEWH... 目录一、简单CASE WHEN函数:二、CASE WHEN条件表达式函数三、常用场景场景1:不同状态展

Python容器类型之列表/字典/元组/集合方式

《Python容器类型之列表/字典/元组/集合方式》:本文主要介绍Python容器类型之列表/字典/元组/集合方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 列表(List) - 有序可变序列1.1 基本特性1.2 核心操作1.3 应用场景2. 字典(D

Linux find 命令完全指南及核心用法

《Linuxfind命令完全指南及核心用法》find是Linux系统最强大的文件搜索工具,支持嵌套遍历、条件筛选、执行动作,下面给大家介绍Linuxfind命令完全指南,感兴趣的朋友一起看看吧... 目录一、基础搜索模式1. 按文件名搜索(精确/模糊匹配)2. 排除指定目录/文件二、根据文件类型筛选三、时间

Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)

《Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)》:本文主要介绍Java导入、导出excel的相关资料,讲解了使用Java和ApachePOI库将数据导出为Excel文件,包括... 目录前言一、引入Apache POI依赖二、用法&步骤2.1 创建Excel的元素2.3 样式和字体2.