实际是个找规律 模拟:自己的思路是枚举一下看小于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;
}
联系客服