HDU 2421 一个数的因数与质因数个数的关系

佚名 7年前 (2019-04-18) 随笔 637人围观抢沙发百度已收录

题面：一个数字的因数的因数的个数的立方和

听起来有点绕

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

就是对于一个数找到它的所有因数对于这些找到的每一个因数再找到它们所有的因数个数然后把这些个数的立方和相加

对于8来说它有4个因数 1 2 4 8

1有1个因数

2有2个因数

4有3个因数

8有4个因数

所以答案为1³+2³+3³+4³=36

对于一般情况，我们这样分析：

首先，找到一个数字的所有因数是比较困难的，我们比较熟悉的方式对一个数进行质因数分解

对于一个数n来说，可以分解为n=aⁱ*b^j*c^k*......的形式且这种形式是唯一的

然后n的因数个数是有多少个呢？对于n任意一个因数，都是由n的这些质因数相乘得到的

举个具体的例子

12=2*2*3=2²*3

如何找到它的所有因数

对于2来说，我们可以不选2，选一个2，选两个2，对于3，可以不选3或者选一个3，不选的就乘1。有人会问这是啥意思？看完下面你就懂

1*1=1

2*1=2

2²*1=4

1*3=3

2*3=6

2²*3=12

大家应该可以看出规律了吧：对于n=aⁱ*b^j*c^k*......的每一因数m，就a而言，m可能包含0个a,1个a,2个a,...i个a

就b而言，m可能包含0个b ... j个b

... ...

所以n共有(i+1)(j+1)(k+1)...个因数

下面就可以解这道题目了：

还是n=aⁱ*b^j*c^k*......这个数

它的因数和因数的个数是

1 1

a 2

a² 3

a³ 4

...

ai i+1

这部分的和就是1³+2³+3³+...（i+1)³

下面继续，考虑上b

b 2

a*b 2*2

a²*b 2*3

...

b2 3

a*b2 3*2

...

^{算上这部分的，个数就是}

[1³+2³+3³+...（i+1)³][1³+2³+3³+...（j+1)³]

以此类推

最后答案是

[1³+2³+3³+...（i+1)³][1³+2³+3³+...（j+1)³][1³+2³+3³+...（k+1)³]...

然后三次方和可以直接用立方和公式求解，然后取模，就可以啦

#include<bits/stdc++.h>
using namespace std;
bool is_prime(long long x){
    if(x==1)
        return false;
    if(x==2||x==3)
        return true;
    if(x%6!=1&&x%6!=5)
        return false;
    int s=sqrt(x);
    for(int i=5;i<=s;i+=6)
        if(x%i==0||x%(i+2)==0)
            return false;
    return true;
}

vector<long long> pfc(long long n){//快速质因数分解 
	vector <long long> st;
	long long i=0;
	if(n==1)
	{
		st.push_back(1);
		return st; 
	} 
	while(i<n)
	{
		if(is_prime(n)){
			st.push_back(n);
			return st;
		}
		for(i=2;i<n;i++)
		{
			if(n%i==0)
			{
				st.push_back(i);
				n/=i;
				break;
			}
			
		}	
	}
	st.push_back(n);
	return st;
}

long long readl(){
	long long ans=0;
	char ch=getchar();
	while(ch<='9'&&ch>='0')
	{
		ans=ans*10+ch-'0';
		ch=getchar();
	}
	return ans;
} 

vector <long long> getsize(long long n){
	vector <long long> st=pfc(n);	
	long long tt=1;
	vector <long long> v;
	for(long long i=1;i<st.size();i++)
	{
		if(st[i]!=st[i-1])
		{
			v.push_back(tt);
			tt=0;	
		} 
		tt++;
	}
	v.push_back(tt);
	return v;
}
int main()
{
	
	long long A,B;
	int cas=1;
	while(true)
	{
		A=readl();
		B=readl();
		if(!(A&&B)) break;
		if(A==1) {
			printf("Case %d: %lld\n",cas++,1);
			continue ;
		}
		vector <long long> v=getsize(A);
		for(long long i=0;i<v.size();i++)
		v[i]=((v[i]%10007)*(B%10007))%10007;
		long long ans=1;
		for(long long i=0;i<v.size();i++)
		{
			v[i]=(v[i]+1)%10007;
			ans*=((v[i]*(v[i]+1)/2)%10007)*((v[i]*(v[i]+1)/2)%10007);
			ans=ans%10007;
		}
		printf("Case %d: %lld\n",cas++,ans);
	}
}