题解 P2557 【[AHOI2002]芝麻开门】

· · 题解

听说有更好的阅读体验

题目大意

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

题目思路

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

约数和定理：

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

对于一个大于 1 正整数 n 可以分解质因数：

n=p1^{a1}*p2^{a2}*p3^{a3}*…*pk^{ak}

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

之后呢， n 的 (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 < 2^{16} 莫非是传说中的 n^2 过百万 肯定是要用 高精。

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

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

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

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

望采纳，谢谢。