杜爷的式子都好神仙啊


三角形

题目

描述

求出周长为$n$,边长为整数的不同三角形的个数.

注意边是无序的,即$3,4,5$和$4,5,3$算同一个三角形.

由于出题人害怕卡不掉乱搞答案可能很大,你只需要输出答案对$10^9+7$取模的结果.

输入输出格式

输入格式

一行一个整数$n$

输出格式

一行一个整数表示答案对$10^9+7$取模的结果.

样例

输入样例1

10

输出样例1

2

输入样例2

100000000

输出样例2

331875002

数据范围

对于$40\%$的数据,$n\leq 10^7$

对于$60\%$的数据,$n\leq 10^9$

对于$100\%$的数据,$1\leq n\leq 10^{18}$

思路

应该是签到题了吧,能不能A完全取决于推出来的式子会不会被卡精度

设三角形三边为$a,b,c$,且$a\le b\le c$。

要成三角形就有$a+b+c=n,a+b>c$。

于是先枚举$a+b$,易知其下界为$\left\lfloor\dfrac{n}{2}\right\rfloor+1$。

上界我们看条件$b\le c$,设$a+b=k$,$c=n-k$,此时$b$的最小值为$\left\lceil\dfrac{k}{2}\right\rceil$,则有$\left\lceil\dfrac{k}{2}\right\rceil\le n-k$。

则其上界为$\left\lfloor\dfrac{2n}{3}\right\rfloor+1$。

再枚举$a$,要满足$a\le b$,其上界为$\left\lfloor\dfrac{k}{2}\right\rfloor$,还要满足$b\le c$。

即$a+b-a\le c$,$k-a\le n-k$。

可知其下界为$2k-n$。

于是答案为$\sum\limits_{i=\lfloor\frac{n}{2}\rfloor+1}^{\lfloor\frac{2n}{3}\rfloor+1}\left\lfloor\dfrac{i}{2}\right\rfloor-2i+n+1$

$\left\lfloor\dfrac{i}{2}\right\rfloor-2i$可以转成等差数列求和,$n+1$乘上就好。

拍一下发现$3|n$时答案总是少$1$,猜测是由于$a=b=c=\dfrac{n}{3}$没算上,还要再加上。

这题取模真的恶心。。。反正复杂度是$O(1)$的随便模。

题解

杜爷の题解

杜爷直接容斥然后一顿推式子。

只会枚举的我瑟瑟发抖。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 100005
#define pn putchar('\n')

const int mod = 1e9 + 7;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
template<typename T>
inline T read(){
    T x=0;
    int y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
#define int long long
signed main(){
    int n=read<long long>(),l=(n>>1)+1,r=((n<<1)/3+1),ans=((n%3==0)+(n%mod+1)*(r%mod-l%mod+1)%mod-(l%mod+r%mod)*(r%mod-l%mod+1)%mod)%mod;
    if(l&1)--l,(ans-=l>>1)%mod;
    if(!(r&1))++r,(ans-=r>>1)%=mod;
    (ans+=(((l>>1)+(r>>1))%mod*((r-l+1>>1)%mod))%mod)%=mod;
    printf("%lld\n",(ans+mod)%mod);
}

直角三角形

题目

描述

求所有周长不超过$n$,边长为整数的直角三角形的个数.注意,边是无序的,换句话说$a-b-c$和$a-c-b$是同一个三角形.

如果你不知道直角三角形的判定方法,可以看这里

输入输出格式

输入格式

一行一个正整数$n$

输出格式

一行一个整数表示答案.

样例

输入样例1

12

输出样例1

1

输入样例2

100

输出样例2

17

输入样例3

100000

输出样例3

64741

数据范围

对于$30\%$的数据,$n\leq 1000$

对于$70\%$的数据,$n\leq 10^6$

对于$100\%$的数据,$n\leq 10^{10}$

提示

这篇文章可能会有帮助

思路

我会$O(n^2)$枚举三边!

获得了$30$分的好成绩。

通过阅读提示里的文章,知道了:

勾股数组:若$a,b,c\in N^*$且$a^2+b^2=c^2$,则$(a,b,c)$称为勾股数组。

本原勾股数组:$a,b,c$没有公因数的勾股数组。

勾股数组定理:若奇数$s,t$满足$s>t\ge 1$且$gcd(s,t)=1$,则$a=st,b=\dfrac{s^2-t^2}{2},c=\dfrac{s^2+t^2}{2}$可构成本原勾股数组。

我会枚举所有奇数!

好像并没有什么改进。。。

一个直角三角形的周长为$a+b+c=st+s^2=s(t+s)$。

枚举构成的三角形周长为$i$,显然$s|i$。

这样我们只要检验一下$i$的每个约数即可,大概能获得$70$分。

然而不知道哪里写挂了没调出来。。。

$zz$的我并没有发现由于周长为$st+s^2$,则$s$只要枚举到$\sqrt{n}$即可。。。

题解

头一回见$odd(i)$($i$为奇数)和$even(i)$($i$为偶数),孤陋寡闻了。。。

杜爷の题解

神仙反演啊,下面基本都是抄的

答案为$\sum\limits_{s,t}[s>t\ge 1][odd(s)][odd(t)][gcd(s,t)=1]\left\lfloor\dfrac{n}{s(s+t)}\right\rfloor$

枚举$d=s+t$:

$=\sum\limits_{s,t,d}[d=s+t][s>t\ge 1][odd(s)][odd(t)][gcd(s,t)=1]\left\lfloor\dfrac{n}{sd}\right\rfloor$

$gcd(s,t)=gcd(s,d-s)=gcd(d,s)$;因为$s,t$均为奇数,所以$d$为偶数。而若$s,t$均为偶数时$d$也为偶数,此时$gcd(s,d)\neq 1$,所以直接把$[odd(s)][odd(t)]$换为$[even(d)]$:

$=\sum\limits_{s,t,d}[d=s+t][s>t\ge 1][even(d)][gcd(s,d)=1]\left\lfloor\dfrac{n}{sd}\right\rfloor$

消掉$[even(d)]$,枚举$2d$:

$=\sum\limits_{s,t,d}[2d=s+t][s>t\ge 1][gcd(s,2d)=1]\left\lfloor\dfrac{n}{2sd}\right\rfloor$

消掉$t$,把$2d=s+t$代入$s>t\ge 1$得:

$=\sum\limits_{s,d}[d<s<2d][gcd(s,2d)=1]\left\lfloor\dfrac{n}{2sd}\right\rfloor$

套路反演:

$=\sum\limits_{s,d,k}[d<s<2d][k|s][k|2d]\mu(k)\left\lfloor\dfrac{n}{2sd}\right\rfloor$

分类$k$的奇偶:

$=\sum\limits_{s,d,k}[d<s<2d][k|s][k|d][odd(k)]\mu(k)\left\lfloor\dfrac{n}{2sd}\right\rfloor+\sum\limits_{s,d,k}[d<s<2d][k|s][\frac{k}{2}|d][even(k)]\mu(k)\left\lfloor\dfrac{n}{2sd}\right\rfloor$

分开算,奇数部分:

$\sum\limits_{s,d,k}[d<s<2d][k|s][k|d][odd(k)]\mu(k)\left\lfloor\dfrac{n}{2sd}\right\rfloor$

$=\sum\limits_{s,d,k}[d<s<2d][k\ge 1][(2k-1)|s][(2k-1)|d]\mu(2k-1)\left\lfloor\dfrac{n}{2sd}\right\rfloor$

$s,d$改为枚举$2k-1$的倍数:

$=\sum\limits_{s,d,k}[d<s<2d][k\ge 1]\mu(2k-1)\left\lfloor\dfrac{n}{2sd(2k-1)^2}\right\rfloor$

令$t=\left\lfloor\dfrac{n}{2(2k-1)^2}\right\rfloor$,给$s,d,k$实际的枚举范围:

$=\sum\limits_{k=1}^{\sqrt{n}}\mu(2k-1)\sum\limits_{d=2}^{\sqrt{t}}\sum\limits_{s=d+1}^{\min\{2d-1,\lfloor\frac{t}{d}\rfloor\}}\left\lfloor\dfrac{t}{sd}\right\rfloor$

设$g(n)=\sum\limits_{i=2}^{\sqrt{n}}\sum\limits_{j=i+1}^{\min\{2i-1,\frac{n}{i}\}}\left\lfloor\dfrac{n}{ij}\right\rfloor$

该部分即为$\sum\limits_{k=1}^{\sqrt{n}}\mu(2k-1)g(t)$

再来看偶数部分:

$\sum\limits_{s,d,k}[d<s<2d][k|s][\frac{k}{2}|d][even(k)]\mu(k)\left\lfloor\dfrac{n}{2sd}\right\rfloor$

$=\sum\limits_{s,d,k}[d<s<2d][2k|s][k|d]\mu(2k)\left\lfloor\dfrac{n}{2sd}\right\rfloor$

$=\sum\limits_{s,d,k}[\dfrac{d}{2}<s<d]\mu(2k)\left\lfloor\dfrac{n}{4sdk^2}\right\rfloor$

令$t’=\left\lfloor\dfrac{n}{4k^2}\right\rfloor$

$=\sum\limits_{k=1}^{\sqrt{n}}\mu(2k)\sum\limits_{d=2}^{\sqrt{2t’}}\sum\limits_{s=\frac{d}{2}+1}^{\min\{d-1,\lfloor\frac{t’}{d}\rfloor\}}\left\lfloor\dfrac{t’}{sd}\right\rfloor$

设$h(n)=\sum\limits_{i=2}^{\sqrt{2n}}\sum\limits_{j=\frac{i}{2}+1}^{\min\{i-1,\lfloor\frac{n}{i}\rfloor\}}\left\lfloor\dfrac{n}{ij}\right\rfloor$

总答案即为$\sum\limits_{k=1}^{\sqrt{n}}\mu(2k-1)g(\left\lfloor\dfrac{n}{2(2k-1)^2}\right\rfloor)+\sum\limits_{k=1}^{\sqrt{n}}\mu(2k)h(\left\lfloor\dfrac{n}{4k^2}\right\rfloor)$

关于$g$和$h$因为比较诡异只能外层暴力内层整除分块算,复杂度是$O(n^{\frac{3}{4}})$的。

答案中$\sum\limits_{k=1}^{\sqrt{n}}$也是暴力算,杜爷用积分算出来复杂度还是$O(n^{\frac{3}{4}})$的。

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 1000001
#define inf 0x3f3f3f3f

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
template<typename T>
inline T read(){
    T x=0;
    int y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int mu[maxn],prime[maxn>>2],cnt;
bool is[maxn];
long long g(long long n){
    long long tp,di,ans=0;
    for(register int i=2;1ll*i*i<=n;++i){
        tp=min((1ll*i<<1)-1,di=n/i);
        for(register int l=i+1,r;l<=tp;l=r+1){
            r=min(tp,di/(di/l));
            ans+=(r-l+1)*(di/l);
        }
    }
    return ans;
}
long long h(long long n){
    long long tp,di,ans=0;
    for(register int i=2;1ll*i*i<=n<<1;++i){
        tp=min(1ll*i-1,di=n/i);
        for(register int l=(i>>1)+1,r;l<=tp;l=r+1){
            r=min(tp,di/(di/l));
            ans+=(r-l+1)*(di/l);
        }
    }
    return ans;
}
int main(){
    is[1]=mu[1]=1;
    for(register int i=2;i<maxn;++i){
        if(!is[i])prime[++cnt]=i,mu[i]=-1;
        for(register int j=1;j<=cnt&&i*prime[j]<maxn;++j){
            is[i*prime[j]]=1;
            if(i%prime[j]==0){mu[i*prime[j]]=0;break;}
            mu[i*prime[j]]=-mu[i];
        }
    }
    long long n=read<long long>(),ans=0;
    for(register int i=1;1ll*i*i<=n;++i)
        ans+=g(n/(2ll*((i<<1)-1)*((i<<1)-1)))*mu[(i<<1)-1]+h(n/(4ll*i*i))*mu[i<<1];
    printf("%lld\n",ans);
}

等腰直角三角形

题目

描述

求$\sum\limits_{i=1}^n\varphi(ik)\pmod {10^9+7}$

输入输出格式

输入格式

一行两个正整数$n$和$k$

输出格式

一行一个整数表示答案对$10^9+7$取模的结果

样例

输入样例

100 100

输出样例

170520

数据范围

对于$20\%$的数据,$n,k\leq 10000$

对于另外$20\%$的数据,$n\leq 10^{10},k\leq 2$

对于再另外$20\%$的数据,$n\leq 10^7,k\leq 10^{10}$

对于$100\%$的数据,$n,k\leq 10^{10}$

思路

刚学到的$\varphi$的性质:$\varphi(ij)=\dfrac{\varphi(i)\varphi(j)gcd(i,j)}{\varphi(gcd(i,j))}$

$n,k\le 10000$直接暴力求每个数的欧拉函数$O(n\sqrt{nk})=n^2$即可重背了遍求单个数的欧拉函数

$k=1$时就是裸的杜教筛。

这是个积性函数虽然我不会证,于是$n\le 10^7$可以考虑线筛。

对于质数$p$,$f(p)=\dfrac{(p-1)\varphi(k)gcd(p,k)}{\varphi(gcd(p,k))},f(p^{m+1})=pf(p^m)$。

提前算出$\varphi(k)$,我们仅对每个质数做$gcd$,复杂度是$O(n)$的。

不知道为啥没想着去线筛它于是只拿到了$30$分。

题解

杜爷の题解

还是反演:

$\sum\limits_{i=1}^n\varphi(ik)$

$=\varphi(k)\sum\limits_{i=1}^n\dfrac{\varphi(i)gcd(i,k)}{\varphi(gcd(i,k))}$

$=\varphi(k)\sum\limits_{i=1}^n\varphi(i)\sum\limits_{d=1}^n\dfrac{[gcd(i,k)=d]d}{\varphi(d)}$

$=\varphi(k)\sum\limits_{d=1}^n\dfrac{d}{\varphi(d)}\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\varphi(id)\sum\limits_{a=1}^{\lfloor\frac{n}{d}\rfloor}[d|k][a|i][a|\frac{k}{d}]\mu(a)$

$=\varphi(k)\sum\limits_{a|k}\mu(a)\sum\limits_{d|\frac{k}{a}}\dfrac{d}{\varphi(d)}\sum\limits_{i=1}^{\lfloor\frac{n}{ad}\rfloor}\varphi(iad)$

令$T=ad$

$=\varphi(k)\sum\limits_{T|k}\sum\limits_{i=1}^{\lfloor\frac{n}{T}\rfloor}\varphi(iT)\sum\limits_{d|T}\mu(\dfrac{T}{d})\dfrac{d}{\varphi(d)}$

设$f(T)=\sum\limits_{d|T}\mu(\dfrac{T}{d})\dfrac{d}{\varphi(d)},S(n,k)=\sum\limits_{i=1}^n\varphi(ik)$

$S(n,k)=\varphi(k)\sum\limits_{T|k}S(\left\lfloor\dfrac{n}{T}\right\rfloor,T)f(T)=\varphi(k)\left(S(n,1)f(1)+\sum\limits_{T|k,T>1}S(\left\lfloor\dfrac{n}{T}\right\rfloor,T)f(T)\right)$

显然$\dfrac{d}{\varphi(d)}$是积性函数,和$\mu$卷起来还是积性函数。

对于质数$p$,$f(p)=\dfrac{1}{p-1},f(p^m)=\dfrac{p^m}{\varphi(p^m)}-\dfrac{p^{m-1}}{\varphi(p^{m-1})}=0$。

于是可以质因数分解求$f(T)$。

$S(n,1)$可以杜教筛,递归计算$S(\left\lfloor\dfrac{n}{T}\right\rfloor,T)$。

杜爷算出来复杂度是$O(d(k)\sqrt{k})$的。

代码

要特判掉$k=1$的情况,否则会一直在$S(n,1)$递归下去。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 20000001
#define inf 0x3f3f3f3f

const int mod = 1e9 + 7;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
template<typename T>
inline T read(){
    T x=0;
    int y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
const int Mod = 3e6 + 7;
#define int long long
struct hash{
    int h[Mod],d[Mod],nex[Mod],cnt;
    long long s[Mod];
    void insert(long long x,int y){
        s[++cnt]=x,x%=Mod,nex[cnt]=h[x],d[h[x]=cnt]=y;
    }
    int find(long long x){
        for(register int i=h[x%Mod];i;i=nex[i])
            if(s[i]==x)return d[i];
        return mod;
    }
}mphi;
int phi[maxn],sum_phi[maxn],prime[maxn>>2],cnt;
bool is[maxn];
long long PHI(long long x){
    if(x<maxn)return phi[x];
    long long ans=x;
    for(register int i=2;1ll*i*i<=x;++i){
        if(x%i==0){
            ans-=ans/i;
            while(x%i==0)x/=i;
        }
    }
    if(x>1)ans-=ans/x;
    return ans;
}
int f(long long x,long long ans){
    for(register int i=2;1ll*i*i<=x;++i){
        if(x%i==0){
            if(x/i%i==0)return 0;
            ans/=i-1,x/=i;
        }
    }
    if(x>1)ans/=x-1;
    return ans;
}
int sphi(long long n){
    if(n<maxn)return sum_phi[n];
    int ans=mphi.find(n);
    if(ans!=mod)return ans;
    ans=(n%mod*(n%mod+1)>>1)%mod;
    for(long long l=2,r;l<=n;l=r+1){
        r=n/(n/l);
        (ans-=1ll*(r-l+1)*sphi(n/l)%mod)%=mod;
    }
    mphi.insert(n,ans);
    return ans;
}
int s(long long n,long long k){
    if(!n)return 0;
    long long phik=PHI(k);
    int F,ans=phik%mod*sphi(n)%mod,p;
    for(register int i=2;i*i<=k&&i<=n;++i){
        if(k%i==0){
            F=f(i,phik);
            if(F)(ans+=1ll*F*s(n/i,i)%mod)%=mod;
            if((p=(k/i))!=i){
                F=f(p,phik);
                if(F)(ans+=1ll*F*s(n/p,p)%mod)%=mod;
            }
        }
    }
    if(k<=n){
        F=f(k,phik);
        if(F)(ans+=F*s(n/k,k)%mod)%=mod;
    } 
    return ans;
}
#undef int
int main(){
    long long n=read<long long>(),k=read<long long>();
    is[1]=phi[1]=sum_phi[1]=1;
    for(register int i=2;i<maxn;++i){
        if(!is[i])prime[++cnt]=i,phi[i]=i-1;
        sum_phi[i]=(sum_phi[i-1]+phi[i])%mod;
        for(register int j=1;j<=cnt&&i*prime[j]<maxn;++j){
            is[i*prime[j]]=1;
            if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    if(k==1)printf("%lld\n",(sphi(n)+mod)%mod);
    else printf("%lld\n",(s(n,k)+mod)%mod);
}