二次剩余(Cipolla’s algorithm)学习笔记

先放资料。


 

前置技能点:
剩余系

剩余系:设模为m,则根据余数可将所有的整数分成m类,分别记成[0],[1],[2],[m-1]
m个数{0,1,2,m-1}称为一个完全剩余系,
每个数称为相应类的代表元。
当m=10(偶数)时候,则{0,1,2,3,4,5,6,7,8,9}是最小非负完全剩余系
{-5,-4,-3,-2,-1,0,1,2,3,4,5} 是绝对值最小完全剩余系
{-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小
{1,2,3,4,5,6,7,8,9,10}是最小正完全剩余系
简化剩余系:在每个剩余类选取至1个与m互素代表元构成简化剩余系。
当m=10则,{0,1,2,3,4,5,6,7,8,9} 完全剩余系
{1,3,7,9}是简化剩余系(x,10)=1
当m=5则,{0,1,2,3,4}为完全剩余系,
{1,2,3,4}是简化剩余系,因为除去余0(正好是倍数)外,其它都互素。
f(m)=欧拉函数=|{t|0<t<m, (t, m)=1}|
=简化剩余系的元素个数

继续阅读“二次剩余(Cipolla’s algorithm)学习笔记”

poj 2356 Find a multiple (剩余类,抽屉原理)

 

http://poj.org/problem?id=2356

题意:有n个数,从中选取若干个(1..n),和能被n整除。问是否有解,无解输出0,有解的话,输出个数以及选择的a[i]( 不是i)

由抽屉原理可知一定有解:
做一个带模的前缀和 sum[i]=(sum[i-1]+a[i])%n
n个数,sum[i]最多有n种。
如果某个sum[i]为0,那么表示从1到i的和能被n整除。
如果所有的sum[i]不为0,那么一共有n个sum[i],n-1个值(1..n-1),一定有sum[i]==sum[j](i<=j)
那么a[i]到a[j]的和一定能被n整除。

poj 3370 Halloween treats (剩余类,抽屉原理)

昨天那道签到的数学题没搞出来不开心.
是时候刷一波数学了
这题题意是说,从n个数中任选m个,使得m个的和为c的倍数.
如果有解,输出选的数的下标,否则输出无解字符串.
抽屉原理的原始描述是,如果有n+1个物品,有n个抽屉,那么至少有一个抽屉有2个物品.
抽屉原理我们可以退出一个结论,对于任意 n个自然数,一定有连续的一段和为n的倍数.
证明如下:
  设这n个自然数分别为a1,a2,a3,a4….an
  处理一个前缀和sum[i] = (sum[i-1] + a[i])%n
  因为n的剩余类有n种,分别为0,1,2…n-1
  所以sum[1],sum[2],sum[3]..sum[n]
  那么sum[1],sum[2],sum[3]…sum[n]最多也有n种.
  我们分情况讨论:
    (1)sum[1],sum[2],sum[3]…sum[n]互不相同,那么一定存在sum[i]=0,也就是前i个数的和为n的倍数.
    (2)情况(1)的反面,也就是存在sum[i]==sum[j]  (i<j),那么 从a[i+1] 到 a[j]的和就是n的倍数.
因为题目中的数据 c<=n ,所以解一定存在.
具体做法就是处理出来一个前缀和%c
然后如果有0,则为解,输出.
否则记录sum[i]%d出现的位置,存在一个数组里
如果sum[i]%d第二次出现,就输出这段下标.
嘛,大括号换风格了….
都写开代码太长了==