「题解」Product

Product ，据说是天津某学校的题目。

题目

题目描述

请快速计算 \(\frac{f(n)}{g(n)}\) 的结果，其中
\[
\begin{cases}
n=\prod p^{e _ i} _ i\\
f(n)=\prod p _ i^{2e _ i+1}\\
g(n)=\sum^n _ {i=1}\frac{n}{\gcd(i,n)}
\end{cases}
\]

每一个测试点有 \(T\) 组数据。

数据范围

时空限制

题解

Product 简单数论题。

思路

先化简 \(g(n)\)，我们显然有
\[
\begin{aligned}
g(n)&=\sum^n _ {i=1}\frac{n}{\gcd(i,n)}\\
&=\sum _ {d\mid n}\frac{n}{d}\varphi(\frac{n}{d})\\
&=\sum _ {d\mid n}d\varphi(d)\\
&=\sum _ {d\mid n}d^2\prod _ {p _ i\in\mathbb{P} _ d}(1-\frac{1}{p _ i})\\
&=\prod _ {p _ i\in\mathbb{P} _ n}(1+\sum^{c _ i} _ {k=1}p^{2k} _ i(1-\frac{1}{p _ i}))\\
&=\prod _ {p _ i\in\mathbb{P} _ n}(1+(1-\frac{1}{p _ i})\sum^{c _ i} _ {k=1}p^{2k} _ i)\\
&=\prod _ {p _ i\in\mathbb{P} _ n}(1+(1-\frac{1}{p _ i})\times\frac{p^2 _ i(1-p^{2c _ i})}{1-p^2 _ i})\\
&=\prod _ {p _ i\in\mathbb{P} _ n}(1+\frac{p _ i-1}{p _ i}\times\frac{p^2 _ i(1-p^{2c _ i})}{1-p^2 _ i})\\
&=\prod _ {p _ i\in\mathbb{P} _ n}(1+\frac{p _ i-1}{p _ i}\times\frac{p^2 _ i(1-p^{2c _ i})}{(1-p _ i)(1+p _ i)})\\
&=\prod _ {p _ i\in\mathbb{P} _ n}(1-\frac{p _ i(1-p^{2c _ i})}{1+p _ i})\\
&=\prod _ {p _ i\in\mathbb{P} _ n}(\frac{1+p _ i}{1+p _ i}-\frac{p _ i(1-p^{2c _ i})}{1+p _ i})\\
&=\prod _ {p _ i\in\mathbb{P} _ n}\frac{1+p _ i-p _ i(1-p^{2c _ i})}{1+p _ i}\\
&=\prod _ {p _ i\in\mathbb{P} _ n}\frac{1+p^{2c _ i+1}}{1+p _ i}
\end{aligned}
\]

考虑答案的式子
\[
\begin{aligned}
\frac{f(n)}{g(n)}&=\frac{\prod _ {p _ i\in\mathbb{P} _ n}(p^{2c _ i+1}+1)}{\prod _ {p _ i\in\mathbb{P} _ n}\frac{1+p^{2c _ i+1}}{1+p _ i}}\\
&=\frac{\prod _ {p _ i\in\mathbb{P} _ n}(p^{2c _ i+1}+1)}{(\frac{\prod _ {p _ i\in\mathbb{P} _ n}(p^{2c _ i+1}+1)}{\prod _ {p _ i\in\mathbb{P} _ n}(1+p _ i)})}\\
&=\prod _ {p _ i\in\mathbb{P} _ n}(1+p _ i)
\end{aligned}
\]

最后得到答案为
\[
\texttt{ans}\equiv\prod _ {p _ i\in\mathbb{P} _ n}(1+p _ i)\pmod{10^9+7}
\]

使用 Pollard’s Rho 即可以 \(\Theta(Tn^\frac{1}{4})\) 的时间复杂度通过这道题目。

代码

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 1000000007
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline ll read(void){
	reg char ch=getchar();
	reg ll res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10ll*res+ch-'0',ch=getchar();
	return res;
}

inline ll add(reg ll a,reg ll b,reg ll mod){
	reg ll sum=a+b;
	return sum>=mod?sum-mod:sum;
}

inline ll mul(reg ll a,reg ll b,reg ll mod){
	reg ll res=0;
	while(b){
		if(b&1)
			res=add(res,a,mod);
		a=add(a,a,mod);
		b>>=1;
	}
	return res;
}

inline ll pow(reg ll x,reg ll exp,reg ll mod){
	reg ll res=1;
	while(exp){
		if(exp&1)
			res=mul(res,x,mod);
		x=mul(x,x,mod);
		exp>>=1;
	}
	return res;
}

const int MAXSIZE=10000+5;

inline bool Miller_Rabin(reg ll n,reg ll base){
	reg ll d=n-1,p=0;
	while(!(d&1))
		d>>=1,++p;
	reg ll cur=pow(base%n,d,n);
    if(cur==1||cur==n-1)
        return true;
	for(reg int i=1;i<=p;++i){
        cur=mul(cur,cur,n);
        if(cur==n-1)
            return true;
    }
	return false;
}

inline bool Miller_Rabin(reg ll n){
    if(n==46856248255981||n<2)
        return false;
    if(n==2||n==3||n==7||n==61||n==24251)
        return true;
    return Miller_Rabin(n,2)&&Miller_Rabin(n,3)&&Miller_Rabin(n,7)&&Miller_Rabin(n,61)&&Miller_Rabin(n,24251);
}

inline ll gcd(reg ll a,reg ll b){
    return b==0?a:gcd(b,a%b);
}

inline ll Pollard_Rho(reg ll n){
    reg ll i=0,k=2,x=rand()%(n-1)+1,y=x;
    reg int c=rand();
    while(true){
        ++i;x=(mul(x,x,n)+c)%n;
        reg ll Gcd=gcd((y-x+n)%n,n);
        if(Gcd!=1&&Gcd!=n)
            return Gcd;
        if(x==y)
            return n;
        if(i==k)
            k<<=1,y=x;
    }
    return n;
}

int tot;
ll fac[MAXSIZE];

inline void Div(reg ll n){
    if(n==1)
        return;
    if(Miller_Rabin(n)){
        fac[++tot]=n;
        return;
    }
    reg ll p=n;
    while(p>=n)
        p=Pollard_Rho(n);
    Div(p),Div(n/p);
    return;
}

inline void Solve(reg ll n){
	tot=0;
	Div(n);
	sort(fac+1,fac+tot+1);
	reg int m=unique(fac+1,fac+tot+1)-(fac+1);
	reg int ans=1;
	for(reg int i=1;i<=m;++i)
		ans=1ll*ans*(fac[i]%MOD+1ll)%MOD;
	printf("%d\n",ans);
	return;
}

int main(void){
	reg int T=read();
	while(T--)
		Solve(read());
	return 0;
}