(T1:facsum)
题目
Mr.Hu最近偶得一函数(f(n) = n^m imes sum_{d|n}{sigma_0(d)mu(frac{n}{d})frac{n}{d}})
求(F(n) = sum_{i=1}^n{f(i)},(nleq 10^7,mleq 10))，答案对(10^9+7)取模
做法
数论函数掠杀我qwq
可以看出右边那个(sum)里面的三个部分都是积性函数，所以它们的乘积也是积性函数，通过计算/打表/瞎猜可知：
当(p)为质数时，有(f(p) = 2-p)
对于(p^x)，有(f(p^x) = -x*p + x + 1)
线性筛一遍即可求解
时间复杂度(O(nlogm))
Code
#include<bits/stdc++.h>
#define N 10000005
#define re register
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
int n,m;
int p[N],d[N],c[N],v[N],cnt;
bool isnotp[N];
template <class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
ll calc(ll x,ll y) {return ((ll)x-x*y+mod+1)%mod;}
void init(int maxn)
{
c[1]=v[1]=1;
isnotp[1]=1;
for(re int i=2;i<=maxn;++i)
{
if(!isnotp[i]) p[++cnt]=i,c[i]=i,d[i]=1,v[i]=2-i;
for(re int j=1;j<=cnt&&(ll)p[j]*i<=maxn;++j)
{
isnotp[p[j]*i]=1;
if(i%p[j]==0)
{
c[p[j]*i]=(ll)c[i]*p[j]%mod;
d[p[j]*i]=d[i]+1;
v[p[j]*i]=v[i/c[i]]*calc(d[p[j]*i],p[j])%mod;
break;
}
c[p[j]*i]=p[j];
d[p[j]*i]=1;
v[p[j]*i]=(ll)v[i]*v[p[j]]%mod;
}
}
}
ll quickpow(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
int main()
{
freopen("facsum.in","r",stdin);
freopen("facsum.out","w",stdout);
init(N-1);
read(n);read(m);
ll ans=0;
for(re int i=1;i<=n;++i)
{
ans=(ans+quickpow(i,m)*v[i])%mod;
}
cout<<(ans%mod+mod)%mod<<endl;
return 0;
}
(T2:group)
题目
Mr.Hu在研究等比数列，他想知道(a^{1,2.....})这样的一个无穷数列对于模(mod)有多少项本质不同，多组数据，(a,modleq 2*10^9)
做法
如果出现了一个(a^n)使得(a^n equiv a)，那么(1)到(n-1)这一段一定就是所有本质不同的项（因为之后的项会循环了），现在就是要求这样一个最小循环节的大小
一般情况下，问题变成解高次同余方程(a^x equiv 1)，这里的(x)即答案，用BSGS即可
需要注意的是，同余方程可能无解，但(x)一定有解（雾），需要特判（模数为1的情况）
时间复杂度(O(Tsqrt{mod}))
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 100007;
int T;
ll a,mod;
struct List
{
int next,to;
ll val;
}l[M<<3]; int hd[M+5],cnt=0;
template <class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
ll quickpow(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1) ret=ret*a%mod;
a=a*a%mod;
b>>=1;
}
return ret;
}
void ins(ll val,int loc)
{
ll k=val%M;
for(int i=hd[k];i;i=l[i].next) if(l[i].to==loc && l[i].val==val) return;
l[++cnt].next=hd[k];
l[cnt].to=loc;
l[cnt].val=val;
hd[k]=cnt;
}
ll query(ll val)
{
ll k=val%M;
for(int i=hd[k];i;i=l[i].next) if(l[i].val==val) return l[i].to;
return -1;
}
ll BSGS(ll a,ll b,ll mod)
{
int p=(int)sqrt(mod)+1;
ll now=1;
for(int i=0;i<p;++i)
{
ins(now,i);
now=now*a%mod;
}
a=quickpow(a,p);
now=a;
for(int i=1;i<=p;++i)//从1开始循环避开a^1
{
int j=query(now);
if(j>=0&&i*p-j>=0) return i*p-j;
now=now*a%mod;
}
return -1;
}
int main()
{
freopen("group.in","r",stdin);
freopen("group.out","w",stdout);
read(T);
while(T--)
{
read(a);read(mod);
memset(hd,0,sizeof(hd));
cnt=0;
printf("%lld
",BSGS(a,1,mod));
}
return 0;
}
(T3:ccount)
题目
Mr.Hu在学习美丽的组合数，他想求(sum_{i=l}^{r}{[C_n^i\% 5=0]},(n,l,rleq 10^{18}))，多组数据
做法
看到(n)那么大还要求组合数，显然(lucas)定理，计数问题选择数位DP，用(lucas)相当于将(n)看做5进制数了，相当于在5进制下做数位DP
如果想到了变为5进制，本题其实是个相当模板的数位DP
时间复杂度(O(T*20*log_5{n}))
Code
#include<bits/stdc++.h>
#define N 100
#define wtcl 0
using namespace std;
typedef long long ll;
int T,C[6][6];
int wei[N],cnt;
int nn[N],sum;
ll n,l,r;
ll f[N][2][2];
template <class T>
void read(T &x)
{
char c;int sign=1;
while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;
while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;
}
void init(ll x)
{
ll c=x;
cnt=0;
while(c) {wei[++cnt]=c%5;c/=5;}
}
ll dfs(int step,bool ok,bool lim)//处理到第step位，是否出现了0，顶上界
{
if(step==0) return ok;
if(f[step][ok][lim]!=-1) return f[step][ok][lim];
ll ret=0;
if(lim)
{
for(int i=0;i<wei[step];++i)
{
int p=C[nn[step]][i];
ret+=dfs(step-1,ok|(p%5==0),0);
}
int p=C[nn[step]][wei[step]];
ret+=dfs(step-1,ok|(p%5==0),1);
}
else
{
for(int i=0;i<5;++i)
{
int p=C[nn[step]][i];
ret+=dfs(step-1,ok|(p%5==0),0);
}
}
return f[step][ok][lim]=ret;
}
ll solve(ll x)//找出所有小于等于x的数满足C(n,i)%5=0
{
if(x==-1) return 0;
memset(wei,0,sizeof(wei));
memset(f,-1,sizeof(f));
init(x);//把x拆了
return dfs(sum,0,1);
}
int main()
{
freopen("ccount.in","r",stdin);
freopen("ccount.out","w",stdout);
C[0][0]=C[1][0]=C[1][1]=1;
for(int i=2;i<=5;++i)
{
C[i][0]=1;
for(int j=1;j<=i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1];
}
read(T);
while(T--)
{
read(l);read(r);read(n);
sum=0;
memset(nn,0,sizeof(nn));
while(n) {nn[++sum]=n%5;n/=5;}
printf("%lld
",solve(r)-solve(l-1));
}
return wtcl;
}
/*
2
1 3 4
1 4 5
*/