math – Tgotp-Blog

2818: Gcd

首先知道

gcd(x,y) =  z

可化为

gcd(x/z,y/z) = 1;

那么令f[i] 为满足 gcd(x,y)= 1 (x,y <= i)的个数

那么答案就为 ∑ f[n/prime[i]]

观察发现 f[i] 为欧拉函数的前缀和。

那么线[......]

Read more

1088: [SCOI2005]扫雷Mine

观察发现,我们枚举最左边的点,他旁边的点的值自然出来,然后能确定整个序列,所以判断一下。

每个点只有两个状态,有雷,无雷,所以,答案只会是三个数0,1,2,解决

c++代码如下:

 

2017年9月12日 0 / /
Tag:  No Tags

T9760 2017

题目背景

四川省ACM 2017 G题

题目大意:

给定四个整数a,b,c,d,a <= x <= b,c <= y <= d

求出有多少对x,y使得x*y是2017的倍数。

题目描述

Given a, b, c, d, find out t[......]

Read more

P1134 阶乘问题

反正肯定知道高位数的答案肯定对结果没影响,所以取适当的位数取模就搞定了。。。

取模数完全靠猜。。。

c++代码如下:

 

扩展欧几里得原理

好文章推荐:http://blog.csdn.net/lincifer/article/details/49391175#扩展欧几里德算法附证明

求exgcd;

¨

 

求gcd(最大公因数的)随便补一[......]

Read more

中国剩余定理

用处的话大概就是一个x%一些y有一些z,根据这些数求出x。

重要的点话应该是:

mj .   Mj*Mj^-1 mod(mj)=1;

求出这个mj^-1,而mj分别等于yj(但是需要满足互质的条件,不互质拆开就好了[......]

Read more

求数因数个数

一个数必定能分解成多个质因数的乘积形式。(懒得证明了)

首先将这个数分解成几个质数的几次幂乘机形式。

然后它的因数就是每个质数幂+1乘积和。

2017年4月17日 0 / /
Tag:  No Tags