杜爷的式子都好神仙啊。
三角形
题目
描述
求出周长为$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);
}