数论综合题。 题目背景 题目背景与题目无关因此省略。题目链接 题目描述 猪王国的文明源远流长,博大精深。 iPig 在大肥猪学校图书馆中查阅资料,得知远古时期猪文文字总个数为 $N$。当...
欧拉函数
神炎皇 题解【数学】【gcd】【欧拉函数】
怎么才能想到可以这样推啊……数学题做少了orz。 问题描述 神炎皇乌利亚很喜欢数对,他想找到神奇的数对。 对于一个整数对\((a,b)\),若满足\(a+b\le n\)且\(a+b\)是\(ab\)的因子,则成为...
洛谷 P3747 相逢是问候 题解【树状数组】【欧拉定理】【快速幂】【平衡树】
一道充分考察了扩展欧拉定理的题目,并且细节要求比较多。 题目描述 Informatik verbindet dich und mich. 信息将你我连结。 B 君希望以维护一个长度为\(n\)的数组,这个数组...
洛谷 P4139 上帝与集合的正确用法 题解【欧拉函数】【数学】
扩展欧拉定理的应用 题目描述 根据一些书上的记载,上帝的一次失败的创世经历是这样的: 第一天, 上帝创造了一个世界的基本元素,称做“元”。 第二天, 上帝创造了一...
数学小知识点【学习笔记】 upd on 2019.7.10
一、线性求逆元 1. $1\sim n$ 的逆元 单独一个数 $\bmod p$ 的逆元是可以用费马小定理($p$ 为质数)或 exgcd 在 $O(\log p)$ 的复杂度内求的。但是如果要求 $1\sim n$ 的逆元,其实用不到 $O(n\log n)$。正如 $O...
洛谷 P2158 [SDOI2008]仪仗队 题解【数学】【gcd/lcm】【欧拉函数】【筛素数】
找规律?? 题目描述 作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的...