标签:数学

Codeforces Round #463 C Permutation Cycle

huangkui 2018年2月16日 No Comments Problem , , ,

题目链接:传送门 Solution 实际上就是求Ax + By = N的非负整数解(x和y都要非负),我是写的扩欧求的,实际上只需要暴力一个一个试就可以了。然后写扩欧的话要注意在用特解求非负整数解 的时候要注意A和B都要除一个gcd,考试的时候没加,然后就愉快地FST,rating暴跌了

AGC007 C – Pushing Balls

huangkui 2018年2月7日 No Comments Problem , , ,

题目链接:传送门 Description 在一条直线上有 n 个球和 n + 1 个坑共 2n + 1 个“物品”,i 个球在第 i 和第i + 1 个坑之间。 球与坑之间是有距离的,这些距离组成了首项为 a,公差为 x 的等差数列。即第i个物品和第 i + 1 个物品之间的距离是 a + (i − 1)x。 小 A 会进行 n 轮操作,每轮操作中,先从剩下的球中等概率地选择一个,然后等概率地选择一个方向,这个球将会朝这个方向滚,直到遇到一个里面 […]

Baby-Step-Gaint-Step(BSGS)算法

huangkui 2018年1月3日 No Comments Algorithm, 未分类 , , ,

模板题:POJ2417 调这道题调了我一下午,第二天实在查不出错把#ifndef去掉就A了。。。。。 大致思想 BSGS这个算法主要是用来解决这个问题: A^x\\equiv B ( mod \\ C)已知ABC, 求x 而最普通的BSGS求解的是C为质数(其实就是相当与AC互质)的情况 对于这个问题,如果直接暴力枚举x的值的话,根据Fermat小定理可以知道A^{\\phi p} \\equiv 1(mod\\ p) 那么我们只要再往下枚举的话 […]

Miller-Rabin素数测试

huangkui 2017年12月31日 No Comments Algorithm, 未分类 , ,

基本算法 Miller-Rabin素数测试其实是基于Fermat小定理的一种素数测试方法,其大致思想如下: Fermat小定理:对于素数p和任意正整数a,有a^{p-1} \\equiv 1(mod\\ p),反过来,如果满足a^{p-1} \\equiv 1(mod\\ p),p就有很大概率是素数 Miller-Rabin:于是,我们不断选取基数b, 计算是否每次都有b^{n – 1} \\equiv 1(mod\\ p),若每次都 […]

Page 1 of 2