题目大意:
给定一个数 \(n\),对于每个 \(n\),都有能整除它的数 \(x\),我们最后要输出的结果是每个 \(x\) 的“难挖指数”的和。
正文:
举一个例子,当 \(x=5\) 时, 有和它互质的数 \(y \in \{1,2,3,4\}\)。
此时我引出一条定理,当 \(x\) 与 \(y\) 互质时,\(x\) 和 \((x-y)\) 也互质。那我们给"\(y\)"和"\((x-y)\)"分到一组,分别是 \(\{1,4\},\{2,3\}\)。
很容易发现,每组的和是 \(x\),有 \(\dfrac{\varphi (x)}{2}\) 组(注意当\(x=1\)或\(2\)时,\(\varphi(x)=1\),需要特判),那\(x\)的难挖指数求出来了。
代码:
ll Ans(ll n)
{
if(n == 1)
{
return 1;
}
ll sum = n, n_ = n;
for (int i = 1; i <= cnt; i++)
{
if(n % prime[i] == 0 )
{
sum = sum * (prime[i] - 1) / prime[i];
for (; n % prime[i] == 0; n /= prime[i]);
}
if(n == 1) break;
}
if(n > 1)
{
sum = sum * (n - 1) / n;
}
return sum * n_ / 2;
}
int main()
{
n = 100000;
init();
for (scanf ("%lld", &t); t--;)
{
ans = 0;
scanf ("%lld", &n);
for (ll i = 1; i * i <= n; i++)
{
if(n % i == 0)
{
ans += Ans(i);
if (i * i != n) ans += Ans(n / i);
}
}
printf("%lld", ans);
puts("");
}
return 0;
}