Description：
小火车励志成为一名辣鸡出题人，但是要成为一名辣鸡出题人，代码必须跑得比谁都快，这样就能把他们都卡常数了！为了锻炼自己，他找到了一位长者——罗长者，罗长者说：“你啊，toosimple！不要想弄一个大新闻，说现在已经‘钦定’了，然后把我批评一番。”小火车坐在高高的骨灰旁边，听长者讲那钦定的事情。
如果一个n位数X（可以有前导0）对所有的k(1<=k<n)都满足X10k mod 10n>X，长者就会钦定这个X，然后长者会产生n2的愉悦度。长者会指定一个n，然后钦定满足条件的1位数，2位数，...，n位数。求长者的愉悦度之和，答案模258280327（2317+1，一个质数）。
https://gmoj.net/senior/#main/show/4533
题解：
考虑一个串，如果它没有循环同构串和它相同，那么它的最小循环同构串就是一个合法的答案。
记(f[n])为长度为(n)的没有循环同构串和自己相同的串个数，那么(f[n]/n)就是长度(n)时的答案。
不难得到dp：
(f[n]=10^n-sum_{d|n~and~d
eq n} f[d])
直接统计(10^{...})的贡献，不难得到：
(f[n]=sum_{d|n}10^d*mu(n/d))
或者用mobius反演推出(f)：
设(g[n])表示长度为(n)可能循环的串数，(g[n]=10^n=sum_{d|n}f[d])
所以(f[n]=sum_{d|n}g[d]*mu(n/d)=sum_{d|n}10^d*mu(n/d))
那么
(Ans=sum_{i=1}^n i*sum_{j|i}10^j*mu(i/j))
(=sum_{i=1}^n mu(i)*i sum_{j=1}^{n/i} 10^j*j)
杜教筛处理(mu(i)*i)的前缀和，后面是高中数列题。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int mo = 258280327;
ll ksm(ll x, ll y) {
ll s = 1;
for(; y; y /= 2, x = x * x % mo)
if(y & 1) s = s * x % mo;
return s;
}
const ll ni2 = ksm(2, mo - 2);
const int N = 1e6 + 5;
int bz[N], p[N], p0, mu[N];
ll s[N];
void sieve(int n) {
mu[1] = 1;
fo(i, 2, n) {
if(!bz[i]) p[++ p0] = i, mu[i] = -1;
for(int j = 1; i * p[j] <= n; j ++) {
int k = i * p[j] % mo;
bz[k] = 1;
if(i % p[j] == 0) {
mu[k] = 0; break;
}
mu[k] = -mu[i];
}
}
fo(i, 1, n) s[i] = (s[i - 1] + mu[i] * i) % mo;
}
ll n;
ll cn1(ll x) {
x %= mo;
return x * (x + 1) % mo * ni2 % mo;
}
const ll ni9 = ksm(9, mo - 2);
ll calc(ll x) {
ll s = (ksm(10, x + 1) - 10) * ni9 - ksm(10, x + 1) * (x % mo);
s = (-s % mo + mo) * ni9 % mo;
return s;
}
const int M = 1960817;
struct hash {
ll h[M], f[M];
int fi[M], nt[M], tot;
ll &operator [] (ll n) {
int y = n % M;
for(int p = fi[y]; p; p = nt[p])
if(h[p] == n) return f[p];
nt[++ tot] = fi[y], fi[y] = tot, h[tot] = n;
return f[tot];
}
int find(ll n) {
int y = n % M;
for(int p = fi[y]; p; p = nt[p])
if(h[p] == n) return 1;
return 0;
}
} h;
ll dg(ll n) {
if(n <= 1e6) return s[n];
if(h.find(n)) return h[n];
ll s = 1;
for(ll i = 2, j; i <= n; i = j + 1) {
j = n / (n / i);
s = (s - (cn1(j) - cn1(i - 1)) * dg(n / i)) % mo;
}
s = (s % mo + mo) % mo;
return h[n] = s;
}
int main() {
sieve(1e6);
scanf("%lld", &n);
ll ans = 0;
for(ll i = 1, j; i <= n; i = j + 1) {
j = n / (n / i);
ans = (ans + (dg(j) - dg(i - 1)) * calc(n / i)) % mo;
}
ans = (ans % mo + mo) % mo;
pp("%lld
", ans);
}