【神秘】PE中利用一些性质简化代码
oscar
2019-07-18 08:09:38
65.连分数的性质
```python
f=[1,2]+[0]*100
for i in range(2,101):
qwq=1
if(i%3==0):
qwq=i//3*2
f[i]=f[i-1]*qwq+f[i-2]
t=f[100]
print(t)
ans=0
while(t>0):
ans+=t%10
t//=10
print(ans)
```
66.64(根号化连分数)+65
[论文](https://wenku.baidu.com/view/7f8fb7d376a20029bd642d0a.html)
[参考资料](https://www.cnblogs.com/Pandaman/p/Diophantine.html)
```python
def sqr(x):
return x*x
from math import sqrt
def chk0(x):
return sqr(int(sqrt(x)+1e-12))==x
def chk(x,y,n):
#print("check ",x,y,n)
if(x*x-n*y*y==1):
#print()
print(x,"^ 2 -",n,"*",y,"^ 2 = 1")
return True
else:
return False
#p/q
ans=0
maxx=0
for i in range(1,1001):
if(chk0(i)):
continue
k=int(sqrt(i)+1e-12)
p=[1,k]+[0]*233
q=[0,1]+[0]*233
if(chk(p[1],q[1],i)):
if(p[1]>maxx):
maxx=p[1]
ans=i
continue
d=i-k*k
x=(k+k)//d
a=x*d-k
#print(d,x,a)
p[2]=p[1]*x+p[0]
q[2]=q[1]*x+q[0]
if(chk(p[2],q[2],i)):
if(p[2]>maxx):
maxx=p[2]
ans=i
continue
for j in range(3,233):
d=(i-a*a)//d
x=(k+a)//d
a=x*d-a
#print(d,x,a)
p[j]=p[j-1]*x+p[j-2]
q[j]=q[j-1]*x+q[j-2]
if(chk(p[j],q[j],i)):
if(p[j]>maxx):
maxx=p[j]
ans=i
break
print(ans)
```
72.简单容斥
```cpp
#include<bits/stdc++.h>
using namespace std;
const int n=1000000;
int cnt=0;
int c[1111111];
int main()
{
c[1]=1;
for(int i=1;i<=n;i++)
for(int j=i+i;j<=n;j+=i)
c[j]-=c[i];
long long ans=0;
for(int i=1;i<=n;i++)
{
ans+=1ll*(n/i)*(n/i)*c[i];
}
cout<<ans/2<<endl;
return 0;
}
```
73.Stern-Brocot tree
```cpp
#include<bits/stdc++.h>
using namespace std;
const int LIM=12000;
int cnt=0;
void gao(int lp,int lq,int rp,int rq)
{
int p=lp+rp,q=lq+rq;
if(p<=LIM&&q<=LIM)
{
cnt++;
gao(lp,lq,p,q);
gao(p,q,rp,rq);
}
}
int main()
{
gao(1,2,1,3);
cout<<cnt<<endl;
return 0;
}
```
75.勾股数的生成
所有勾股数都形如$k(m^2-n^2), 2kmn, k(m^2+n^2)$的形式
map去重即可
78.分拆数
听说$p(n)=\sum_{k\neq0}(-1)^{k+1}p(n-k(3k-1)/2)$
未验证