dataisland‘s blog

暴力证明

2017-02-25 18:48:16    106    0    0

证明:

存在两个正无理数x和y,xy是有理数。
如果 (2)2 为有理数,那么x=y=2

如果(2)2 为无理数,那么x=(2)2 , y=2xy=2

证明完毕。

[NOI2016]循环之美

2016-12-05 22:05:40    230    2    0

[NOI2016]循环之美

首先有一个结论,

ans=i=1Nj=1M[gcd(i,j)=1][gcd(i,K)=1]

然后来推公式吧
ans====i=1,gcd(i,K)=1Mj=1N[gcd(i,j)=1]i=1,gcd(i,K)=1Mj=1Nd|gcd(i,j)μ(d)dmin(N,M)i=1,gcd(di,K)=1Mdj=1Nd1d,gcd(d,K)=1min(N,M)μ(d)Ndi=1M[gcd(i,K)=1]

countK(n)=ni=1[gcd[i,K)=1]


则当n小于等于K时暴力计算,
大于时显然有countK(n)=nKcountK(K1)+countK(n mod K)

现在原式变为

d,gcd(d,K)=1min(N,M)μ(d)countK(M)Nd


Sum(k,n)=d,gcd(d,k)=1nμ(d)

若能快速算出这个值则可以对后面的部分分块计算.

Project Euler 441

2016-11-30 13:10:48    188    0    0

The inverse summation of coprime couples

Problem:

For an integer M

, we define R(M) as the sum of 1/(p·q) for all the integer pairs p and q which satisfy all of these conditions:

1p<qMp+qMp and q are coprime.


We also define S(N) as the sum of R(i) for 2iN.
We can verify that S(2)=R(2)=1/2, S(10)6.9147 and S(100)58.2962

.

Find S(107)

. Give your answer rounded to four decimal places.


An Equation

2016-11-29 13:35:12    68    0    1

1+21+31+41+=3
Let me provide a full and simple proof here