【神秘】PE中利用一些性质简化代码

2019-07-18 08:09:38


65.连分数的性质

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

论文 参考资料

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.简单容斥

#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

#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)$

未验证