1 ╰⋛⋋⊱⋋吳⋌⊰⋌⋚╯

尚未进行身份认证

你是我荒唐青春里唯一的认真

等级
TA的排名 9w+

POJ 2142 The Balance (拓展欧几里得)

DescriptionMs.IyoKiffa-Australishasabalanceandonlytwokindsofweightstomeasureadoseofmedicine.Forexample,tomeasure200mgofaspirinusing300mgweightsand700mgweights,shecanp...

2019-10-12 20:38:56

POJ 2891 + POJ 2115

DescriptionElinaisreadingabookwrittenbyRujiaLiu,whichintroducesastrangewaytoexpressnon-negativeintegers.Thewayisdescribedasfollowing:Choosekdifferentpositiveintegersa1,a...

2019-10-10 22:05:38

POJ 1061 + POJ 1006

POJ1061青蛙的约会http://poj.org/problem?id=1061Description两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳...

2019-10-09 15:31:11

拓展中国剩余定理

本文参考自:https://www.cnblogs.com/zwfymqz/p/8425731.html我们知道,中国剩余定理是用来解同余方程组f(x)={x≡c1(mod m1)x≡c2(mod m2)……………x≡cr(mod mr)f(x)=\left\{\begin{aligned}x≡c_1(mod\m_1)\\x≡c_2(mod\m...

2019-09-27 21:07:33

中国剩余定理

模板:x=∑i=1npi∗Nqi∗[(Nqi)−1]qi\sum_{i=1}^np_i*\fracN{q_i}*[(\fracN{q_i})^{-1}]_{q_i}∑i=1n​pi​∗qi​N​∗[(qi​N​)−1]qi​​intp[maxn],q[maxn],n;intexgcd(inta,intb,int&x,int&y){if(...

2019-09-24 23:49:12

扩展欧几里得、线性同余方程、中国剩余定理

拓展欧几里得欧几里得算法(辗转相除法):用于计算两个整数的最大公约数,其原理依赖于:定理:gcd(a,b)=gcd(b,a%b)证明:设a=kb+r,其中k和r分别为a除以b得到的商和余数。则有r=a-kb成立。设d为a和b的一个公约数,那么有r=a-kb,得d也是r得一个约数。因此d是b和r的...

2019-09-23 20:12:29

POJ 3101 Astronomy(分子最小公倍数+圆周追击)

DescriptionTherearenplanetsintheplanetarysystemofstarX.TheyorbitstarXincircularorbitslocatedinthesameplane.Theirtangentvelocitiesareconstant.Directionsoforbitingofall...

2019-09-19 16:41:58

石油大 2019秋个人训练赛1 D 卡片

题目描述你有一叠标号为1到n的卡片。你有一种操作,可以重排列这些卡片,操作如下:1.将卡片分为前半部分和后半部分。2.依次从后半部分,前半部分中各取一张卡片,放到新的序列中。例如,对卡片序列(1,2,3,4,5,6)操作后的结果为(4,1,5,2,6,3)。现在你有一个初始为(1,2,3,⋯,n)的卡片序列,你需要求出进行m次操作之后第x个位置上的卡片的标号。输入第一行包含三个非负...

2019-09-18 17:01:38

石油大 2019秋个人训练赛1 C DNA

题目描述小X身为奆老,兴趣爱好广泛,他还非常喜欢研究DNA序列……小X进行了一项关于DNA序列研究,发现人某条染色体上的一段DNA序列中连续的k个碱基组成的碱基序列与做题的AC率有关!于是他想研究一下这种关系。现在给出一段DNA序列,请帮他求出这段DNA序列中所有连续k个碱基形成的碱基序列中,出现最多的一种的出现次数。输入第一行为一段DNA序列,保证DNA序列合法,即只含有A,G,C,T...

2019-09-17 23:37:41

石油大 2019秋个人训练赛1 B 种树

事实上,小X邀请两位奆老来的目的远不止是玩斗地主,主要是为了抓来苦力,替他的后花园种树……小X的后花园是环形的,他想在花园周围均匀地种上n棵树,但是奆老花园的土壤当然非同寻常,每个位置适合种的树都不一样,一些树可能会因为不适合这个位置的土壤而损失观赏价值。小X最喜欢3种树,这3种树的高度分别为10,20,30。小X希望这一圈树种得有层次感,所以任何一个位置的树要比它相邻的两棵树的高度都高或者都...

2019-09-17 23:15:20

石油大 2019秋个人训练赛1 A 斗地主

题目描述众所周知,小X是一个身材极好、英俊潇洒、十分贪玩成绩却依然很好的奆老。这不,他又找了他的几个好基友去他家里玩斗地主了……身为奆老的小X一向认为身边人和自己一样的厉害,他坚信你和他一样有未卜先知的能力,他在他们玩完斗地主后,告诉了你他们的最终得分,希望你猜出他们最少玩了几局牌?注意:小X他们至少玩了1局斗地主。以下是斗地主的规则:发完牌后三人依次叫牌,可叫1分、2...

2019-09-17 22:58:22

fzu1753 Another Easy Problem(多组C(n,m)求解gcd)

传送门:http://acm.fzu.edu.cn/problem.php?pid=1753ProblemDescription小TT最近学习了高斯消元法解方程组,现在他的问题来了,如果是以下的方程,那么应该如何解呢?C(n1,m1)==0(modM)C(n2,m2)==0(modM)C(n3,m3)==0(modM)…C(nk,mk)==0(modM)小TT希望...

2019-09-16 21:49:10

最大公约数 + 最大公倍数

两个数的gcd:辗转相除法lcm:a*b/gcd(a,b)intgcd(inta,intb){ returnb==0?a:gcd(b,a%b);}intlcm(inta,intb){ intg=gcd(a,b); returna*b/g; }快速gcdintqgcd(inta,intb){ if(a==0)return...

2019-09-16 20:44:31

阶乘的因子个数

求n!中有多少个质因子p10!中质因子2的个数:10!1234567891010!中有因子21的数010101010110!中有因子22的数000100010010!中有因子23的数0000000100因此10!中质因子2的个数有5+2+1=8个。仔细思考,n!中有(n/p+...

2019-09-16 17:23:47

unordered_系列

在c++11中出现了一些有用的容器,其中包括了两(三)个非常实用的容器:unordered_map&unordered_set/unordered_multiset其实现的操作与map&set/multiset差不多,只是我们知道map和set实现的是O(logn)进行实现一个映射,其中内置的实现是红黑树,而unordered_map&unordered_...

2019-09-15 19:18:02

POJ 3358 Period of an Infinite Binary Expansion

传送门:http://poj.org/problem?id=3358DescriptionLet{x}=0.a1a2a3…bethebinaryrepresentationofthefractionalpartofarationalnumberz.Supposethat{x}isperiodicthen,wecanwrite{x}=0.a...

2019-09-12 20:21:22

法雷级数

定义法雷级数,是指每一行从0/1开始,以1/1结尾,其他数自左至右将所有的真分数按增加顺序排列;第n行是由所有分母小于或等于n的真分数组成,我们称为n阶法雷级数(法里数列)。如下表:F10/11/12F20/11/21/13F30/11/32/31/14F40/11/41/31/22/33/41/15F50/1...

2019-09-11 14:18:48

POJ 2478 Farey Sequence

传送门:http://poj.org/problem?id=2478DescriptionTheFareySequenceFnforanyintegernwithn>=2isthesetofirreduciblerationalnumbersa/bwith0<a<b<=nandgcd(a,b)=1arran...

2019-09-09 22:46:38

阶与原根学习笔记

本博客参考于:https://www.cnblogs.com/cytus/p/9296661.html阶  阶的定义:设m>1,且gcd(a,m)=1,那么使得ar≡1(modm)成立最小的正整数r称为,a对模m的阶,记作δm(a)。相关定理:定理一:  若m>1,并且gcd(a,m)=1,又满足an≡1(modm),则δ...

2019-09-08 15:48:02

互质和欧拉函数

互质  ∀\forall∀a,b∈N,若gcd(a,b)==1,则称a,b互质。欧拉函数  1~N中与N互质的数的个数被称作欧拉函数,记作ϕ(N)。  若在算术直奔定理中,N=p1c1p2c2……pmcn,则:  ϕ(N)=N*p1−1p1{{p1-1}\over{p1}}p1p1−1​*p2−1p2{{p2-1}\over{p2}}...

2019-09-05 21:39:56

查看更多

勋章 我的勋章
  • 新人勋章
    新人勋章
    用户发布第一条Blink获赞超过3个即可获得
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。