数论相关公式

ACM模版

数论相关公式

欧拉定理

对于互质的整数a和n,有a^φ(n) ≡ 1(mod n)

费马定理

a是不能被质数p整除的正整数,有a^(p-1) ≡ 1(mod p)

Polya定理

设G是p个对象的一个置换群,用k种颜色去染这p个对象,若一种染色方案在群G的作用下变为一种方案,则这两个方案当作是同一种方案,这样的不同染色方案数为:
L = 1 / |G| x ∑(k^C(f)), f ∈ G

C(f)为循环节,|G|表示群的置换方法数。

对于n个位置的手镯,有n种旋转置换和n种翻转置换。
对于旋转置换:
C(f[i]) = gcd(n, i),i表示旋转i颗宝石以后,i = 0时,gcd(n, 0) = n;
对于翻转置换:
如果n为偶数:则有n / 2个置换C(f) = n / 2,有n / 2个置换C(f) = n / 2 + 1;如果n为奇数:则有n个置换C(f) = n / 2 + 1。

欧拉函数 φ(n)

φ(n)积性函数,对于一个质数p和正整数k,有
φ(p^k) = p^k - p^(k-1) = (p - 1)p^(k - 1) = p^k(1 - 1 / p)

当n > 1时,1 … n中与n互质的整数和为nφ(n) / 2。

2n 位数

len=(int)(nlong10(2))+1,(2n1)

默慈金数 HVD 问题

m[i]={ i,m[i1](2i+1)+m[i2](3i3)i+2,if i{ 1,2}if i>2
全部评论

相关推荐

02-08 20:56
已编辑
南京工业大学 Java
在等offer的比尔很洒脱:我也是在实习,项目先不说,感觉有点点小熟悉,但是我有点疑问,这第一个实习,公司真的让实习生去部署搭建和引入mq之类的吗,是不是有点过于信任了,我实习过的两个公司都是人家正式早搭好了,根本摸不到部署搭建的
点赞 评论 收藏
分享
03-28 14:34
中南大学 Java
网易互娱明天的笔试是在一天之内任意选时间作答,那不就等于说可以抄答案?那为什么要发笔试?美团也说不拿笔试卡人,那为什么要发笔试?觉得学生们很有时间是吗? 还有那些笔试全A了没有进面的,笔试的意义到底在哪里?
no_work_no_life:网易互娱的笔试本来就很简单 美团的确实不按笔试刷人,但是笔试是捞人的重要依据,尤其对于双非学生……我一面的时候面试官直接说是看我笔试成绩还可以就把我捞起来了……
投递美团等公司6个岗位 >
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务