费马小定理(可求乘法逆元)

发表于 算法模板 分类,标签:
 内容为:假如p是质数,且gcd(a,p)=1,那么a^(p-1)≡1(modp)。即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。 使用:如果需要求得(a/b)%M的值。 由费马小定理得到如果b与M互质,则有b^(M-1) ≡1(modM) ,所以有b*b^(M-2) ≡1(modM)。那么b关于模M的乘法逆元为b^(M-2)。所以(a/b)modM=((a/b)modM)*((b*b^(M-2))modM)=(a/b)*(b*b^(M-2))modM =(a*(b^(M-2)))modM。然后利用快速幂快速得到b^(M-2)的值就可以了。 ...

L3-015. 球队“食物链”(2017年天梯赛初赛)

发表于 图论 分类,标签: 天梯赛
 某国的足球联赛中有N支参赛球队,编号从1至N。联赛采用主客场双循环赛制,参赛球队两两之间在双方主场各赛一场。联赛战罢,结果已经尘埃落定。此时,联赛主席突发奇想,希望从中找出一条包含所有球队的“食物链”,来说明联赛的精彩程度。“食物链”为一个1至N的排列{T1 T2 ...TN },满足:球队T1战胜过球队T2,球队T2战胜过球队T3,……,球队T(N-1)战胜过球队TN,球队TN战胜过球队T1。现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”,请找出字典序最小的。注:排列{a1 a2 ...aN }在字典序上小于排列{b1 b2 ...bN },当且仅当存在整数K(1<=K<=N),满足:aK <bK且对于任意小于K的正整数i,a...

L3-013. 非常弹的球(2017年天梯赛初赛)

发表于 数论 分类,标签: 天梯赛
 刚上高一的森森为了学好物理,买了一个“非常弹”的球。虽然说是非常弹的球,其实也就是一般的弹力球而已。森森玩了一会儿弹力球后突然想到,假如他在地上用力弹球,球最远能弹到多远去呢?他不太会,你能帮他解决吗?当然为了刚学习物理的森森,我们对环境做一些简化:假设森森是一个质点,以森森为原点设立坐标轴,则森森位于(0,0)点。小球质量为w/100千克(kg),重力加速度为9.8米/秒平方(m/s2)。森森在地上用力弹球的过程可简化为球从(0,0)点以某个森森选择的角度ang(0<ang<pi/2)向第一象限抛出,抛出时假设动能为1000焦耳(J)。小球在空中仅受重力作用,球纵坐标为0时可视作落地,落地时损失p%动能并反弹。地面可视为刚体,忽略小球形状、空气阻力及摩擦阻力等。森森为你准备的公式:动能公式:E=m*v2 /2牛顿力学公式:F...

L2-020. 功夫传人(2017年天梯赛初赛)

发表于 搜索 分类,标签: 天梯赛
 一门武功能否传承久远并被发扬光大,是要看缘分的。一般来说,师傅传授给徒弟的武功总要打个折扣,于是越往后传,弟子们的功夫就越弱……直到某一支的某一代突然出现一个天分特别高的弟子(或者是吃到了灵丹、挖到了特别的秘笈),会将功夫的威力一下子放大N倍——我们称这种弟子为“得道者”。这里我们来考察某一位祖师爷门下的徒子徒孙家谱:假设家谱中的每个人只有1位师傅(除了祖师爷没有师傅);每位师傅可以带很多徒弟;并且假设辈分严格有序,即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z,每向下传承一代,就会减弱r%,除非某一代弟子得道。现给出师门谱系关系,要求你算出所有得道者的功力总值。输入格式:输入在第一行给出3个正整数,分别是:N(<=105)——整个师门的总人数(于是每个人从0到N-1编号,祖师爷的编号为0);Z——祖师爷的功力值(不...

L2-019. 悄悄关注(2017年天梯赛初赛)

发表于 STL容器 分类,标签: 天梯赛
 新浪微博上有个“悄悄关注”,一个用户悄悄关注的人,不出现在这个用户的关注列表上,但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探,根据某人的关注列表和其对其他用户的点赞情况,扒出有可能被其悄悄关注的人。输入格式:输入首先在第一行给出某用户的关注列表,格式如下:人数N用户1用户2……用户N其中N是不超过5000的正整数,每个“用户i”(i=1,...,N)是被其关注的用户的ID,是长度为4位的由数字和英文字母组成的字符串,各项间以空格分隔。之后给出该用户点赞的信息:首先给出一个不超过10000的正整数M,随后M行,每行给出一个被其点赞的用户ID和对该用户的点赞次数(不超过1000),以空格分隔。注意:用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户,在点赞信息中也没有重复用户。输出格式:我们认为被该用户点赞次数大于其点赞平均数、...

L2-018. 多项式A除以B(2017年天梯赛初赛)

发表于 数论 分类,标签: 天梯赛
 这仍然是一道关于A/B的题,只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R,其中R的阶数必须小于B的阶数。输入格式:输入分两行,每行给出一个非零多项式,先给出A,再给出B。每行的格式如下:Ne[1]c[1]...e[N]c[N]其中N是该多项式非零项的个数,e[i]是第i个非零项的指数,c[i]是第i个非零项的系数。各项按照指数递减的顺序给出,保证所有指数是各不相同的非负整数,所有系数是非零整数,所有整数在整型范围内。输出格式:分两行先后输出商和余,输出格式与输入格式相同,输出的系数保留小数点后1位。同行数字间以1个空格分隔,行首尾不得有多余空格。注意:零多项式是一个特殊多项式,对应输出为“000.0”。但非零多项式不能输出零系数(包括舍入后为0.0)的项。在样例中,余多项式其实有常数项“-1/27”,但因其舍入后为0.0,故不输出。输入样例:...

L2-017. 人以群分(2017年天梯赛初赛)

发表于 模拟 分类,标签: 天梯赛
 社交网络中我们给每个人定义了一个“活跃度”,现希望根据这个指标把人群分为两大类,即外向型(outgoing,即活跃度高的)和内向型(introverted,即活跃度低的)。要求两类人群的规模尽可能接近,而他们的总活跃度差距尽可能拉开。输入格式:输入第一行给出一个正整数N(2<=N<=105)。随后一行给出N个正整数,分别是每个人的活跃度,其间以空格分隔。题目保证这些数字以及它们的和都不会超过231。输出格式:按下列格式输出:Outgoing #: N1Introverted #: N2Diff = N3其中N1是外向型人的个数;N2是内向型人的个数;N3是两群人总活跃度之差的绝对值。输入样例1:1023 8 10 99 46 23...

5-12 监控 (30分)

发表于 数论 分类,标签:
 某国的安全部门监控了全国的数据流,该部门的程序员接到一个任务,恐怖组织会给手下发送一个数字序列A,其中由n个正整数组成,而其中任何两个值Ai和Aj都可以求它们的余数x=AimodAj,(其中1<=i,j<=n,Ai>=Aj)。所有x中,最大的x就是破译机密的秘钥。程序员的任务就是找到这个最大的x。输入格式:第一行是一个正整数n,第二行由n个小于等于10^6106的正整数组成1 ≤ n ≤ 2·10^5105输出格式:输出找到的最大值。输入样例:31 3 10输出样例:1又是水过!!代码:#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define eps&nb...

5-11 灯 塔 (30分)

发表于 数论 分类,标签:
 这一刻心如大海;如迎风的帆沿着海湾;在洒满银子的海面;我是一艘孤单的船;你是否已经在那里;安静的等待着;你是否已经在这里;冰冷的燃烧着。-----彭坦《灯塔》这首歌曲描述的是海岸边上的灯塔,可以把灯塔的灯光想象为一个圆锥形投射到海面上的船帆上(船帆可以想象为一个二维平面)。下面给定船帆上的n个点坐标,n<=1000。求解灯塔的灯光垂直打在这个船帆上,需要直径至少多大的圆,才能够将所有点包含在其中(圆心不一定在原点)。输入格式:第一行为一个正整数n,1<=n<=1000接下来的这n行为n个整数对x,y,0=<x,y<=10^6106输出格式:一个正整数,为包含n个点的圆最小直径的平方。输入样例:20 22 0输出样例:8思路:这题我是水过去的,下面代码遇到极限数据肯定过不了的,只供参考。代码:#incl...

5-6 家谱处理 (30分)

发表于 分类,标签:
 人类学研究对于家族很感兴趣,于是研究人员搜集了一些家族的家谱进行研究。实验中,使用计算机处理家谱。为了实现这个目的,研究人员将家谱转换为文本文件。下面为家谱文本文件的实例:John  Robert    Frank    Andrew  Nancy    David家谱文本文件中,每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代,而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例,John这个家族最早的祖先,他有两个子女Robert和Nancy,Robert有两个子女Frank和Andrew,Nancy只有一个子女David。...