ZOJ 1889 Ones

题意

给你一个数n,n不能被2,5整除,问你n的最小的每个数位全是1的倍数有多少位。

思路

同余定理,另外这个题保证有解,所以相信自己,暴力出奇迹。

代码

 

SGU 126 Boxes

题意

http://www.nocow.cn/index.php/Translate:Sgu/126,翻译版。

思路

我是手写一些找规律,所以我也没办法细讲。

http://www.nocow.cn/index.php/Sgu/126详细题解,说是一个数论题,因为我是找规律所以代码肯定是写不严的,如果你需要严格证明请移步那边。

代码

 

SGU 107 987654321 problem

题意

给你n,让你输出n位数中平方后尾数是987654321的数的个数。

思路

一个数,只考虑最后i位,那么这个数平方之后的最后i位和这个数的最后i位平方后的最后i位相同,所以我们只要考虑1~9位数中谁的平方最后9位是987654321就可以了,本地打个表,发现只有8个数符合要求,接下来,对于10位数,我们就有98=72种组合对于11位数就是908=720种组合,这样我们就发现了,超过10位数的话,就在73后面补上n-10个零就行了,这样大数时也搞定了。

代码

 

HDU 4961 Boring Sum

智商鸿沟不可越系列。。。

思路是这样:首先对于1~100000每一个数生成一个约数表,方便以后查询,我们再建立一个int数组为vis,尺寸100000。接下来对于输入的数组,从左往右扫描,对于每一个数,如果vis[这个数]有值,说明当前数左端有倍数存在,最近的倍数就是这个vis值,没有的话,就是这个数本身,接下来读取当前数的每一个约数,对于每一个约数,当前数都是他们的倍数,所以更新vis[每一个约数]的值为当前数就可以了。
接下来方向反过来,从右到左扫描,算出c值,最统一出答案,小心别爆了int就行。

SGU 102 Coprimes

这个题是欧拉函数:http://baike.baidu.com/view/107769.htm,正好就是这货的定义,说实话我都不知道欧拉函数是啥,打表又没意思了。。。

简单的说就是这个数挨个乘上(n-1)/n,n是不同的质因数。

贴一个求欧拉函数更好的姿势:

降幂公式 a^b %c= a^(b%phi(c)+phi(c)) %c (b>=phi(c))

这个是意外收获,可以用到欧拉函数的地方。

SGU 105 Div3

如果每一位加合等于3的话,这个数也可以被3整除。

然后打个表找下循环节发现是XOOXOOXOO这样的,直接简单判定一下实现就好了。

POJ 3518 Prime Gap

埃氏筛法,没啥好说的嗯。

Scroll to top