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

听起来有点绕

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

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

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

1有1个因数 

2有2个因数

4有3个因数

8有4个因数

所以答案为13+23+33+43=36

对于一般情况,我们这样分析:

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

对于一个数n来说,可以分解为n=ai*bj*ck*......的形式且这种形式是唯一的

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

举个具体的例子

12=2*2*3=22*3

如何找到它的所有因数

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

1*1=1

2*1=2

22*1=4

1*3=3

2*3=6

22*3=12

大家应该可以看出规律了吧:对于n=ai*bj*ck*......的每一因数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=ai*bj*ck*......这个数

它的因数和因数的个数是

1 1

a 2

a2 3

a3 4

...

ai i+1

这部分的和就是13+23+33+...(i+1)3

下面继续,考虑上b

b 2

a*b 2*2

a2*b 2*3

...

b2 3

a*b2 3*2

...

算上这部分的,个数就是

[13+23+33+...(i+1)3][13+23+33+...(j+1)3]

以此类推

最后答案是

[13+23+33+...(i+1)3][13+23+33+...(j+1)3][13+23+33+...(k+1)3]...

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

#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);
	}
} 

  

扫码关注我们
微信号:SRE实战
拒绝背锅 运筹帷幄