L1-046. 整除光棍

发表于 数论 分类,标签: 天梯赛
 这里所谓的“光棍”,并不是指单身汪啦~说的是全部由1组成的数字,比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如,111111就可以被13整除。现在,你的程序要读入一个整数x,这个整数一定是奇数并且不以5结尾。然后,经过计算,输出两个数字:第一个数字s,表示x乘以s是一个光棍,第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。提示:一个显然的办法是逐渐增加光棍的位数,直到可以整除x为止。但难点在于,s可能是个非常大的数——比如,程序输入31,那么就输出3584229390681和15,因为31乘以3584229390681的结果是111111111111111,一共15个1。输入格式:输入在一行中给出一个不以5结尾的正奇数x(<1000)。输出格式:在一行中输出相应的最小的s和n,其间以1个空格分...

51nod-1119 机器人走方格 V2

发表于 数论 分类,标签:
 基准时间限制:1 秒空间限制:131072 KB分值: 10 难度:2级算法题 收藏 关注M*N的方格,一个机器人从左上走到右下,只能向右或向下走。有多少种不同的走法?由于方法数量可能很大,只需要输出Mod10^9+7的结果。Input第1行,2个数M,N,中间用空格隔开。(2 <= m,n <= 1000000)Output输出走法的数量 Mod 10^9 + 7。Input示例2 3Output示例3思路:仔细观察发现其实是求C(n+m-2,m-1),求这个组合,因为mod是10^9+7是素数,所以可用费马小定理求乘法逆元。代码:#include<bits/stdc++.h>usi...

51nod-1126 求递推序列的第N项(矩阵快速幂)

发表于 数论 分类,标签:
 有一个序列是这样定义的:f(1)=1,f(2)=1,f(n)=(A*f(n-1)+B*f(n-2))mod7.给出A,B和N,求f(n)的值。Input输入3个数:A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)Output输出f(n)的值。Input示例3 -1 5Output示例6思路:矩阵快速幂,直接套模板。代码:#include<bits/stdc++.h>using namespace std;#define LL long long#defin...

51nod-1315 合法整数集

发表于 数论 分类,标签:
 一个整数集合S是合法的,指S的任意子集subS有Fun(SubS)!=X,其中X是一个固定整数,Fun(A)的定义如下:A为一个整数集合,设A中有n个元素,分别为a0,a1,a2,...,an-1,那么定义:Fun(A)=a0ora1or...oran-1;Fun({})=0,即空集的函数值为0.其中,or为或操作。现在给你一个集合Y与整数X的值,问在集合Y至少删除多少个元素能使集合Y合法?例如:Y={1,2,4},X=7;显然现在的Y不合法,因为1or2or4=7,但是删除掉任何一个元素后Y将合法。所以,答案是1.Input第一行两个整数N,X,其中N为Y集合元素个数,X如题所述,且1<=N<=50,1<=X<=1,000,000,000.之后N行,每行一个整数yi,即集合Y中的第i个元素,且1<=yi<...

51nod-1417 天堂里的游戏

发表于 数论 分类,标签:
 多年后,每当Noder看到吉普赛人,就会想起那个遥远的下午。Noder躺在草地上漫无目的的张望,二楼的咖啡馆在日光下闪着亮,像是要进化成一颗巨大的咖啡豆。天气稍有些冷,但草还算暖和。不远的地方坐着一个吉普赛姑娘,手里拿着塔罗牌,带着耳机,边上是她的狗。狗看起来有点凶,姑娘却漂亮。Noder开始计算各种搭讪方式的成功概率,然而狗的存在......。奇怪的事情发生了,姑娘自己走了过来,把耳机戴在Noder的耳朵上,里面播放着:“......Knock-knock-knockin'onheaven'sdoor......”。姑娘冲他诡异的一笑,Noder只觉得自己眼前一阵眩晕,然后就站在了天堂的门口。正当Noder惊魂未定的时候,走来一个美女,要求和他一起玩个数学游戏。美女提议:“让我们各自亮出硬币的一面,或正或反。如果我们都是正面,那么我给你A元,如果我们都...

51nod-1629 B君的圆锥

发表于 数论 分类,标签:
 B君要用一个表面积为S的圆锥将白山云包起来。B君希望包住的白山云体积尽量大,B君想知道体积最大可以是多少。注意圆锥的表面积包括底面和侧面。Input一行一个整数,表示表面积S。(1 <= S <= 10^9)Output一行一个实数,表示体积。Input示例8Output示例1.504506思路:首先要知道圆锥表面积公司和体积公式;        面积公式:(r是底面圆半径,l是母线长度,,h为圆锥体的高)体积公式:求最大体积,首先要有S,求的h=,然后带入到V中。         可见当t=b/(-2*a)时达到抛物线的最大值,...

1013 3的幂的和

发表于 数论 分类,标签:
 基准时间限制:1 秒空间限制:131072 KB分值: 20 难度:3级算法题 收藏 关注求:3^0+3^1+...+3^(N)mod1000000007Input输入一个数N(0 <= N <= 10^9)Output输出:计算结果Input示例3Output示例40https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1013代码:#include <bits/stdc++.h>using namespace std;#define INF 0x3f3f3f3f#define eps ...

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-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,故不输出。输入样例:...

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...