【原】约数

余数为0

实际是个找规律 模拟：自己的思路是枚举一下看小于8的情况：对于3：8-2 88-1 888-0；对于5：8-3 88-3重复了所以基本找不到了(因为均为这两个数的倍数)；对于7：8-1 88-4 888-6 8888-5 88888-2 888888-0。实际上在手算的过程中，就发现，上一次的余数乘10后贡献到下一次的计算中，(比如7：8-18-48-68-58-28 看上面的余数)。所以就是个模拟了。水一波。

set<ll> b;
int n, cs = 1;
while (scanf("%d", &n) && n)
{
    int cnt = 0;
    ll k = 8, t;
    bool flag = true;
    b.clear();// 初始化
    while (flag)
    {
        cnt++;
        if (k % n == 0) flag = false;
        else {
            t = k % n;
            if (b.count(t))
            {
                flag = false;
                cnt = 0;
            }
            else
            {
                b.insert(t);
                k = t * 10 + 8;//余数
            }               
        }
    }
    printf("Case %d: %d\n", cs++, cnt);
}

约数和定理

对于一个大于1正整数n可以分解质因数：n=p₁^a₁ *p₂^a₂ *p₃^a₃*…*pk^a_k,则由 约数个数定理可知n的正约数有(a₁+1)(a₂+1)(a₃+1)…(a_k+1)个，那么n的(a₁+1)(a₂+1)(a₃+1)…(a_k+1)个正约数的和为：

证明：易知p₁^a₁的约数有:p₁^0, p₁^1, p₁^2..p₁^a_1，共(a₁+1)个；同理：pk^a_k的约数有:pk^0, pk^1, pk^2......pk^a_k 。实际上n的约数是在p₁^a₁、p₂^a₂、...、pk^a_k每一个的约数中分别挑一个相乘得来，可知共有(a₁+1)(a₂+1)(a₃+1)…(a_k+1)种挑法，即约数的个数。 由加黑字体可知它们的和为：f(n)=(p₁^0+p₁^1+p₁^2+......+p₁^a₁) (p₂^0+p₂^1+p₂^2+…p₂^a₂) … (pk^0+pk^1+pk^2+…pk^a_k) 引用自百度百科。

约数和

约数和定理：需要注意的一个地方就是对于Sum(p, k)在往下递归的时候，不能一次一次向下减-尝试了一下-堆栈溢出 又要用到数学：在k为奇数的时候-公式可以改变形式而简化运算。以下Sum简写为S。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod = 9901;

int Ksm(int a, int b)

{// log(50*1e6) = 25  125*1e7

    int res = 1; a %= mod;

    while(b)

    {

        if (b&1) res = res * a % mod;

        a = a * a % mod;

        b >>= 1;

    }

    return res;

}

int Sum(int p, int k)

{// ksm 和sum 计算时过程中不需要mod 结果已经小于mod 

    if (k == 0) return 1;

    if (k%2==0) return (1 + p%mod*Sum(p, k-1))%mod;// p%mod

    return (1+Ksm(p, k/2+1)) * Sum(p, k/2)%mod;

}

int main()

{

    int a, b, res = 1;

    scanf("%d %d", &a, &b);

    for (int i = 2; i <= a; ++i)

    {

        int s = 0;

        while (a % i == 0)

        {

            s++;

            a /= i;

        }

        if (s) res = res * Sum(i, s*b) %mod;//%mod i^(s*b)

    }

    if (a == 0) res = 0;

    printf("%d\n", res);

    return 0;

}