题意
给定两个整数 (n,m)，求
[sumlimits_{i=1}^{n}frac{1}{prodlimits_{j=i}^{i+m-1}j}
]
( exttt{Data Range:}1leq n+mleq 500)
题解
小学奥数，裂项相消。
比如说有如下例子：
[frac{1}{1 imes2 imes3}=frac{1}{2}left(frac{1}{1 imes2}-frac{1}{2 imes 3}
ight)
]
考虑以这个作为范例来 generalize 一下
[frac{1}{prodlimits_{j=i}^{i+m-1}j}=frac{1}{m-1}left(frac{1}{prodlimits_{j=i}^{i+m-2}j}-frac{1}{prodlimits_{j=i+1}^{i+m-1}j}
ight)
]
然后求和就好了，注意到右边是叠缩求和，直接用最后一项减去第一项即可。
[sumlimits_{i=1}^{n}frac{1}{prodlimits_{j=i}^{i+m-1}j}=frac{1}{m-1}sumlimits_{i=1}^{n}left(frac{1}{prodlimits_{j=i}^{i+m-2}j}-frac{1}{prodlimits_{j=i+1}^{i+m-1}j}
ight)=frac{1}{m-1}left(frac{1}{prodlimits_{j=1}^{m-1}j}-frac{1}{prodlimits_{j=n+1}^{n+m-1}j}
ight)
]
接下来考虑如何不写高精除高精来通过这个题。
显然括号内的东西通分是可以靠分子分母的质因数分解形式的。
于是只要先算出括号内分子分母的质因数分解形式，再用高精乘算出实际分子，减去 (1) 之后再质因数分解。最后分子分母抵掉就好了。
所以这个时候只需要考虑高精除低精和高精模低精两个操作就好了。
代码
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef long long int li;
const ll MAXN=2e5+51,BASE=1000000000;
const li BASE2=(li)BASE*BASE;
struct BigInt{
vector<ll>v;
ll neg;
BigInt();
BigInt(const string &x);
BigInt(const char *x);
BigInt(ll x);
BigInt(li x);
BigInt(const BigInt &x);
inline void setup();
inline void setupStr(const char *str);
inline BigInt& reduce();
inline ll isZero()const;
inline string toString()const;
inline void op()const;
inline BigInt &operator =(const string &x);
inline BigInt &operator =(const char *x);
inline BigInt &operator =(ll x);
inline BigInt &operator =(li x);
inline BigInt &operator =(const BigInt &x);
inline ll compareAbs(const BigInt &x)const;
};
ll n,m,c;
BigInt f,g;
ll fn[MAXN],fd[MAXN];
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-')
{
ch=getchar();
}
if(ch=='-')
{
neg=-1;
ch=getchar();
}
while(isdigit(ch))
{
num=(num<<3)+(num<<1)+(ch-'0');
ch=getchar();
}
return num*neg;
}
inline void BigInt::setup()
{
neg=0,v.clear(),v.push_back(0);
}
inline void BigInt::setupStr(const char *str)
{
ll len;
char token[10];
setup(),len=strlen(str),*str=='-'?neg=1,++str,--len:1,token[9]=0;
if(!len||(len==1&&*str=='0'))
{
return (void)(neg=0);
}
v.clear();
for(register int i=1;i*9<=len;i++)
{
memcpy(token,str+(len-i*9),9),v.push_back((ll)(strtol(token,NULL,10)));
}
if(len%9)
{
memcpy(token,str,len%9),token[len%9]=0;
v.push_back((ll)(strtol(token,NULL,10)));
}
reduce();
}
inline ll BigInt::isZero()const
{
return v.size()==1&&!v.back();
}
inline BigInt& BigInt::reduce()
{
while(v.size()>1&&!v.back())
{
v.pop_back();
}
return isZero()?neg=0:1,*this;
}
inline string BigInt::toString()const
{
string res;
char token[10];
ll c=v.size()-1;
neg&&!this->isZero()?res.push_back('-'):(void)1;
for(sprintf(token,"%d",v[c]);res+=token,c--;sprintf(token,"%09d",v[c]));
return res;
}
inline void BigInt::op()const
{
return (void)(cout<<this->toString());
}
BigInt::BigInt()
{
setup();
}
BigInt::BigInt(const string &x)
{
this->setupStr(x.c_str());
}
BigInt::BigInt(const char *x)
{
this->setupStr(x);
}
BigInt::BigInt(ll x)
{
setup(),x<0?(neg=1,x=-x):1,v.back()=x%BASE;
x>=BASE?v.push_back(x/BASE):(void)1;
}
BigInt::BigInt(li x)
{
setup(),x<0?(neg=1,x-=x):1,v.back()=x%BASE;
x>=BASE?v.push_back(x/BASE%BASE):(void)1;
x>=BASE2?v.push_back(x%BASE2):(void)1;
}
BigInt::BigInt(const BigInt &x)
{
neg=x.neg,v=x.v;
}
inline BigInt& BigInt::operator =(const string &x)
{
return this->setupStr(x.c_str()),*this;
}
inline BigInt& BigInt::operator =(const char *x)
{
return this->setupStr(x),*this;
}
inline BigInt& BigInt::operator =(ll x)
{
setup(),x<0?(neg=1,x=-x):1,v.back()=x%BASE;
return x>=BASE?v.push_back(x/BASE):(void)1,*this;
}
inline BigInt& BigInt::operator =(li x)
{
setup(),x<0?(neg=1,x=-x):1,v.back()=x%BASE;
x>=BASE?v.push_back(x/BASE%BASE):(void)1;
return x>=BASE2?v.push_back(x%BASE2):(void)1,*this;
}
inline BigInt& BigInt::operator =(const BigInt &x)
{
neg=x.neg,v=x.v,*this;
}
inline ll BigInt::compareAbs(const BigInt &x)const
{
if(v.size()!=x.v.size())
{
return (v.size()<x.v.size())?-1:1;
}
for(register int i=v.size()-1;i>=0;i--)
{
if(v[i]!=x.v[i])
{
return (v[i]<x.v[i])?-1:1;
}
}
return 0;
}
inline BigInt unsignedAdd(BigInt &x,BigInt &y)
{
BigInt res;
ll mx=max(x.v.size(),y.v.size()),carry=0;
x.v.resize(mx+1),y.v.resize(mx+1),res.v.resize(mx+1);
for(register int i=0;i<=mx;i++)
{
(res.v[i]=x.v[i]+y.v[i]+carry)>=BASE?res.v[i]-=BASE,carry=1:carry=0;
}
return x.reduce(),y.reduce(),res.reduce();
}
inline BigInt unsignedSub(BigInt &x,BigInt &y)
{
BigInt res;
ll mx=max(x.v.size(),y.v.size()),carry=0;
x.v.resize(mx+1),y.v.resize(mx+1),res.v.resize(mx+1);
for(register int i=0;i<=mx;i++)
{
(res.v[i]=x.v[i]-y.v[i]+carry)<0?res.v[i]+=BASE,carry=-1:carry=0;
}
return x.reduce(),y.reduce(),res.reduce();
}
inline BigInt operator +(BigInt x,BigInt y)
{
BigInt res;
res=x.neg==y.neg?unsignedAdd(x,y):unsignedSub(x,y);
return res.neg=x.neg!=y.neg?(x.compareAbs(y)>=0?x.neg:y.neg):x.neg,res;
}
inline BigInt operator +=(BigInt &x,BigInt y)
{
return x=x+y,x;
}
inline BigInt operator -(BigInt x,BigInt y)
{
BigInt res;
res=x.neg==y.neg?unsignedSub(x,y):unsignedAdd(x,y);
return res.neg=x.neg==y.neg?(x.compareAbs(y)>=0?x.neg:y.neg):x.neg,res;
}
inline BigInt operator -=(BigInt &x,BigInt y)
{
return x=x-y,x;
}
inline BigInt operator *(BigInt x,ll u)
{
BigInt res;
ll mx=x.v.size(),carry=0;
x.v.resize(mx+1),res.v.resize(mx+1),res.neg=x.neg,u<0?res.neg^=1,u=-u:1;
for(register int i=0;i<=mx;i++)
{
res.v[i]=((li)x.v[i]*u+carry)%BASE,carry=((li)x.v[i]*u+carry)/BASE;
}
return x.reduce(),res.reduce();
}
inline BigInt operator *(BigInt x,BigInt y)
{
if(x.isZero()||y.isZero())
{
return BigInt();
}
BigInt res;
ll n=x.v.size(),m=y.v.size(),j,k;
li cur=0,carry=0;
res.neg=x.neg^y.neg,res.v.resize(n+m);
for(register int i=0;i<n+m;i++)
{
for(i<m?(j=0,k=i):(j=i-m+1,k=m-1);j<n&&k>=0;j++,k--)
{
cur+=(li)x.v[j]*y.v[k],carry+=cur/BASE,cur%=BASE;
}
res.v[i]=cur,cur=carry%BASE,carry/=BASE;
}
return res.reduce();
}
inline BigInt operator /(BigInt x,ll u)
{
BigInt res;
li cur=0;
res.neg=x.neg,u<0?res.neg^=1,u=-u:1,res.v.resize(x.v.size()+1);
for(register int i=x.v.size()-1;i>=0;i--)
{
cur=cur*BASE+x.v[i],cur-=(li)(res.v[i]=cur/u)*u;
}
return res.reduce();
}
inline li operator %(BigInt x,ll u)
{
li cur=0;
for(register int i=x.v.size()-1;i>=0;i--)
{
cur=cur*BASE+x.v[i],cur-=(li)(cur/u)*u;
}
return cur;
}
inline BigInt qpow(BigInt base,ll exponent)
{
BigInt res=1;
while(exponent)
{
if(exponent&1)
{
res=res*base;
}
base=base*base,exponent>>=1;
}
return res;
}
int main()
{
n=read(),m=read(),f=g=1;
for(register int i=n+1;i<=n+m-1;i++)
{
c=i;
for(register int j=2;j<=sqrt(c);j++)
{
while(c%j==0)
{
fd[j]++,fn[j]++,c/=j;
}
}
c!=1?fd[c]++,fn[c]++:1;
}
for(register int i=1;i<=m-1;i++)
{
c=i;
for(register int j=2;j<=sqrt(c);j++)
{
while(c%j==0)
{
fn[j]--,c/=j;
}
}
c!=1?fn[c]--:1;
}
for(register int i=1;i<=501;i++)
{
f=f*qpow(i,fn[i]),fn[i]=0;
}
f=f-1,fd[m-1]++;
for(register int i=2;i<=501;i++)
{
while(f%i==0)
{
fn[i]++,f=f/i;
}
}
for(register int i=1;i<=501;i++)
{
if(fd[i]>fn[i])
{
g=g*qpow(i,fd[i]-fn[i]);
}
if(fn[i]>fd[i])
{
f=f*qpow(i,fn[i]-fd[i]);
}
}
f.op(),puts(""),g.op();
}