1 条题解

  • 0
    @ 2025-8-24 21:39:02

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar JJA_
    whk好难whk好难whk好难whk好难whk好难whk好难whk好难whk好难whk好难whk好难

    搬运于2025-08-24 21:39:02，当前版本为作者最后更新于2020-10-18 20:06:31，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    听说有更好的阅读体验

    题目大意

    输入 a,ka,k ，输出 aka^k 的约数和。

    题目思路

    要切掉这道题，你首先需要知道，约数和定理是什么。

    约数和定理：

    听起来很高大尚，其实很简单：

    对于一个大于 11 正整数 nn 可以分解质因数：

    n=p1a1∗p2a2∗p3a3∗…∗pkakn=p1^{a1}*p2^{a2}*p3^{a3}*…*pk^{ak}

    基本的分解质因数的定义，不会的话自己看这里。

    之后呢， nn 的 (a1+1)(a2+1)(a3+1)…(ak+1)(a_1+1)(a_2+1)(a_3+1)…(a_k+1) 个正约数的和为

    $$f(n)=(p1^0+p1^1+p1^2+...+p1^a1)(p2^0+p2^1+p2^2+...+p2^a2)+(pk^0+pk^1+pk^2+...+pk^ak) $$

    证明可以看百度百科。

    之后，再看看数据范围， 1<=n<216 1<= n < 2^{16} 莫非是传说中的 n2n^2 过百万 肯定是要用 高精。

    那我们来复习一下高精，高精其实就是类似竖式一样，但是是使用string类型进行运算。举个例子，

    $$\begin{aligned}221\\\dfrac{+111}{332}\end{aligned} $$

    就是右对齐，然后每位分别相加，注意进位当然由于技术原因我没对齐，请见谅。

    那么，高精加法的式子就推导出来，

    string add(string s1, string s2)
{
    int n = s1.length(), m = s2.length();
    for (int i = 0; i < n; i ++) a[i] = s1[n-1-i] - '0';
    for (int i = 0; i < m; i ++) b[i] = s2[m-1-i] - '0';
    int len = max(n, m) + 1;
    for (int i = n; i < len; i ++) a[i] = 0;
    for (int i = m; i < len; i ++) b[i] = 0;
    for (int i = 0; i < len; i ++) res[i] = 0;
    for (int i = 0; i < len; i ++)
	{
        res[i] += a[i] + b[i];
        if (res[i] >= 10)
		{
            res[i+1] += res[i] / 10;
            res[i] %= 10;
        }
    }
    int i = len-1;
    while (res[i] == 0 && i > 0) i --;
    string s = "";
    for (; i >= 0; i --)
	{
        char c = (char) (res[i] + '0');
        s += c;
    }
    return s;
}

    然后你就发现，你能AC掉这道题，简直是双倍经验对不对

    那么减法的式子也很好推，

    $$\begin{aligned}221\\\dfrac{-111}{110}\end{aligned} $$

    就是注意右对齐和退位。

    string sub(string s1, string s2)
{
    int n = s1.length(), m = s2.length();
    for (int i = 0; i < n; i ++) a[i] = s1[n-1-i] - '0';
    for (int i = 0; i < m; i ++) b[i] = s2[m-1-i] - '0';
    int len = max(n, m);
    for (int i = n; i < len; i ++) a[i] = 0;
    for (int i = m; i < len; i ++) b[i] = 0;
    for (int i = 0; i < len; i ++) res[i] = 0;
    for (int i = 0; i < len; i ++) {
        res[i] += a[i] - b[i];
        if (res[i] < 0) {
            res[i+1] --;
            res[i] += 10;
        }
    }
    int i = len-1;
    while (res[i] == 0 && i > 0) i --;
    string s = "";
    for (; i >= 0; i --) {
        char c = (char) (res[i] + '0');
        s += c;
    }
    return s;
}

    但是注意，一定是大的减小的，所以计算前注意一下。

    接下来乘和除的模板就直接给出了：

    bool cmp(string s1, string s2)
{
    int n = s1.length(), m = s2.length();
    int i;
    for (i = 0; i < n-1 && s1[i] == '0'; i ++);
    s1 = s1.substr(i);
    for (i = 0; i < m-1 && s2[i] == '0'; i ++);
    s2 = s2.substr(i);
    if (s1.length() != s2.length()) return s1.length() < s2.length();
    return s1 < s2;
}

string div(string s1, string s2)
{
    string s = "", t = "";
    int n = s1.length(), m = s2.length();
    bool flag = false;
    for (int i = 0; i < n; i ++)
	{
        s += s1[i];
        int num = 0;
        while (cmp(s, s2) == false)
		{
            num ++;
            s = sub(s, s2);
        }
        if (num > 0)
		{
            flag = true;
            char c = (char)(num + '0');
            t += c;
        }
        else if (flag)
		{
            t += '0';
        }
    }
    if (t.length() == 0) t = "0";
    while (s[0] == '0' && s.length() > 1) s = s.substr(1);
    return t;
}

string mul(string s1, string s2)
{
    int n = s1.length(), m = s2.length();
    for (int i = 0; i < n; i ++) a[i] = s1[n-1-i] - '0';
    for (int i = 0; i < m; i ++) b[i] = s2[m-1-i] - '0';
    int len = n + m;
    for (int i = n; i < len; i ++) a[i] = 0;
    for (int i = m; i < len; i ++) b[i] = 0;
    for (int i = 0; i < len; i ++) res[i] = 0;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            res[i+j] += a[i] * b[j];
    for (int i = 0; i < len; i ++) {
        res[i+1] += res[i] / 10;
        res[i] %= 10;
    }
    int i = len-1;
    while (res[i] == 0 && i > 0) i --;
    string s = "";
    for (; i >= 0; i --) {
        char c = (char) (res[i] + '0');
        s += c;
    }
    return s;
}

    但是注意，在开头先

    const int maxn = 100010;//这个量可以改动
int a[maxn], b[maxn],res[maxn];

    来辅助运算。

    但是在讲主函数前，先讲一下，如何在数字和字符串之间进行转换，比如将一个int值转化成一个string字符串。

    我们将用到stringstream。

    //stringstream具体使用
int i=114514;
string str;
stringstream ss;
ss>>i;
ss<<str;
cout<<str;

    这样将会输出 114514。

    那么用法就很显然，和cin>>差不多含义，这个将数据插入了数字流中，并赋值给了字符串。很方便对不对。

    最后，就是题目代码实现。

    首先，我们需要一个分解质因数的代码，记录因子的个数和数值。相信这个大家都会，先int f[65550];//由于题目大小，最多到这里即可，之后的不用我说了，看代码就行，相信都看得懂。

    int f[maxn];//maxn==65550
void work(int n)
{
	for(int i=2;i<=maxn;i++)
	{
		if(n<=1)
		return;
		while(n%i==0)
		{
			n/=i;f[i]++;
		}
	}
}

    之后，只需要依照题意计算即可，代码：

    for(int i=2;i<=maxn;i++)
	{
		if(f[i]!=0)
		{
			string s;
			stringstream ss;
			ss<<i;
			ss>>s;
			c[i]="1";
			for(int j=1;j<=f[i]*k+1;j++)
			{ 
				c[i]=mul(c[i],s);
			}
			ss.clear();
			c[i]=sub(c[i],"1");
			string sum;
			ss<<i-1;
			ss>>sum;
			c[i]=div(c[i],sum);
		}
	}
	for(int i=2;i<=maxn;i++)
	{ 
		if(f[i]!=0)
		{ 
			ans=mul(ans,c[i]);
		}
	}
	cout<<ans;

    于是就愉快地AC了

    完整代码：

    #include<bits/stdc++.h>
#define maxn 65550
using namespace std;
int a[maxn], b[maxn],res[maxn];
string sub(string s1, string s2)
{
    int n = s1.length(), m = s2.length();
    for (int i = 0; i < n; i ++) a[i] = s1[n-1-i] - '0';
    for (int i = 0; i < m; i ++) b[i] = s2[m-1-i] - '0';
    int len = max(n, m);
    for (int i = n; i < len; i ++) a[i] = 0;
    for (int i = m; i < len; i ++) b[i] = 0;
    for (int i = 0; i < len; i ++) res[i] = 0;
    for (int i = 0; i < len; i ++) {
        res[i] += a[i] - b[i];
        if (res[i] < 0) {
            res[i+1] --;
            res[i] += 10;
        }
    }
    int i = len-1;
    while (res[i] == 0 && i > 0) i --;
    string s = "";
    for (; i >= 0; i --) {
        char c = (char) (res[i] + '0');
        s += c;
    }
    return s;
}
string add(string s1, string s2)
{
    int n = s1.length(), m = s2.length();
    for (int i = 0; i < n; i ++) a[i] = s1[n-1-i] - '0';
    for (int i = 0; i < m; i ++) b[i] = s2[m-1-i] - '0';
    int len = max(n, m) + 1;
    for (int i = n; i < len; i ++) a[i] = 0;
    for (int i = m; i < len; i ++) b[i] = 0;
    for (int i = 0; i < len; i ++) res[i] = 0;
    for (int i = 0; i < len; i ++)
	{
        res[i] += a[i] + b[i];
        if (res[i] >= 10)
		{
            res[i+1] += res[i] / 10;
            res[i] %= 10;
        }
    }
    int i = len-1;
    while (res[i] == 0 && i > 0) i --;
    string s = "";
    for (; i >= 0; i --)
	{
        char c = (char) (res[i] + '0');
        s += c;
    }
    return s;
}
bool cmp(string s1, string s2)
{
    int n = s1.length(), m = s2.length();
    int i;
    for (i = 0; i < n-1 && s1[i] == '0'; i ++);
    s1 = s1.substr(i);
    for (i = 0; i < m-1 && s2[i] == '0'; i ++);
    s2 = s2.substr(i);
    if (s1.length() != s2.length()) return s1.length() < s2.length();
    return s1 < s2;
}

string div(string s1, string s2)
{
    string s = "", t = "";
    int n = s1.length(), m = s2.length();
    bool flag = false;
    for (int i = 0; i < n; i ++)
	{
        s += s1[i];
        int num = 0;
        while (cmp(s, s2) == false)
		{
            num ++;
            s = sub(s, s2);
        }
        if (num > 0)
		{
            flag = true;
            char c = (char)(num + '0');
            t += c;
        }
        else if (flag)
		{
            t += '0';
        }
    }
    if (t.length() == 0) t = "0";
    while (s[0] == '0' && s.length() > 1) s = s.substr(1);
    return t;
}

string mul(string s1, string s2)
{
    int n = s1.length(), m = s2.length();
    for (int i = 0; i < n; i ++) a[i] = s1[n-1-i] - '0';
    for (int i = 0; i < m; i ++) b[i] = s2[m-1-i] - '0';
    int len = n + m;
    for (int i = n; i < len; i ++) a[i] = 0;
    for (int i = m; i < len; i ++) b[i] = 0;
    for (int i = 0; i < len; i ++) res[i] = 0;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < m; j ++)
            res[i+j] += a[i] * b[j];
    for (int i = 0; i < len; i ++) {
        res[i+1] += res[i] / 10;
        res[i] %= 10;
    }
    int i = len-1;
    while (res[i] == 0 && i > 0) i --;
    string s = "";
    for (; i >= 0; i --) {
        char c = (char) (res[i] + '0');
        s += c;
    }
    return s;
}
int f[maxn];
void work(int n){
	for(int i=2;i<=maxn;i++)
	{
		if(n<=1)
		return;
		while(n%i==0)
		{
			n/=i;f[i]++;
		}
	}
}
string c[maxn];
int main()
{
	string ans="1";
	int n,k,a;
	scanf("%d%d",&n,&k);
	work(n);
	for(int i=2;i<=maxn;i++)
	{
		if(f[i]!=0)
		{
			string s;
			stringstream ss;
			ss<<i;
			ss>>s;
			c[i]="1";
			for(int j=1;j<=f[i]*k+1;j++)
			{ 
				c[i]=mul(c[i],s);
			}
			ss.clear();
			c[i]=sub(c[i],"1");
			string sum;
			ss<<i-1;
			ss>>sum;
			c[i]=div(c[i],sum);
		}
	}
	for(int i=2;i<=maxn;i++)
	{ 
		if(f[i]!=0)
		{ 
			ans=mul(ans,c[i]);
		}
	}
	cout<<ans;
}

    望采纳，谢谢。

    • 1

    [AHOI2002] 芝麻开门

    信息

    ID
    1598
    时间
    1000ms
    内存
    125MiB
    难度
    4
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 22ms