Regional 2015-Asia Changchun-B Count a× b
タイトル:http://acm.nenu.edu.cn/regional-2015/files/2015/10/problemset_2051015.pdf
注：f(m)は0≦a、b問題：（64ビットの符号なし整数変数の演算は、モデル264の意味での演算と見なすことができる）g（n）の形を見ると、f（m）が積関数であれば、f（a）＝f（b）があり、g（n）の表現は次のように書き換えられます。
g(n)=Σm(=m)=(f(1)+f(p 1)+f(p 21)+⋯+f(pk 11))＝（f(1)+f(p 2)+f(p 22)+f(pk 22))⋯(f(1)+f(t)+f(p 2)+f(p 2)
上式はこのように理解できます。
nの因子
m
mに対応する質量係数の次のべき乗は一定以下である。
n対応する素数べき乗は、上記積の括弧ごとに1つの数字を選択し、乗算すると1つの数字に対応します。
f(m)は重くも漏れもないと思います。
これでいいです
O（n−−−√）エニュメレート・ファクタのプロセスは、変換される。
O（logn）エニュメレーションの質因子のプロセス。
この問題の中の
f（m）は積性ではないので、その定義は積関数の反対側であるべきだと考えやすいです。
定義
h(m)は満足を表す
0≦a、bm|abの二元組
（a，b）の個数は明らかにあります。
f(m)=m 2−h(m)では、
m 2は明らかに積関数です。計算を考慮します。
h(m)の時、見つけにくくないです。
aと
bの異なる素数の間には影響がありません。それぞれの素数を計算して掛け算原理を利用します。
h(m)は積性ですので、知っているならば
h(pk)はどのように計算すれば、上述の転化過程を利用できますか？
O(logn)解を求める
先に考える
nの全因子
m対応の
m 2の和は、上式で直接計算すればいいです。
もう少し考えてみます
h(m)は、明らかに
aと
b値を取る範囲は、
0≦a、b1≦a、b≦mは答えを変えません。
考慮する
m=pkの場合、令
a=pta⋅ラ、b=ptb⋅rbは、
ラ≦pk−ta且（ラ，p）=1，
rb≦pk−tbであり、（rb，p）＝1である。実は、固定したら
たと
tb
（a，b）の個数は直接計算できます。
ϕ（pk−ta）⋅ϕ（pk−tb）
今求めているのは
h(m)=h(pk)=Σta=0 kΣtb=0 k[ta+tb≧k]⋅ϕ（pk−ta）⋅ϕ（pk−tb）=Σta=0 kΣtb=0 k[ta+tb≦k]⋅ϕ（pta）⋅ϕ(ptb)=Σi=0 kΣj=0 iϕ（pj）⋅ϕ(pk−j)=1＋Σi=1 k(i＋1)pi−2 ipi−1＋(i−1)pi−2=(k＋1)pk−1
さらに一歩進んで
Σki=0 h(pi)=(k+1)pk。
前処理ができます。
O(n−−−√)以内の素数、一回だけ
O(logn)答えを計算します。
コード:
注：f(m)は0≦a、b
g(n)=Σm(=m)=(f(1)+f(p 1)+f(p 21)+⋯+f(pk 11))＝（f(1)+f(p 2)+f(p 22)+f(pk 22))⋯(f(1)+f(t)+f(p 2)+f(p 2)
上式はこのように理解できます。
nの因子
m
mに対応する質量係数の次のべき乗は一定以下である。
n対応する素数べき乗は、上記積の括弧ごとに1つの数字を選択し、乗算すると1つの数字に対応します。
f(m)は重くも漏れもないと思います。
これでいいです
O（n−−−√）エニュメレート・ファクタのプロセスは、変換される。
O（logn）エニュメレーションの質因子のプロセス。
この問題の中の
f（m）は積性ではないので、その定義は積関数の反対側であるべきだと考えやすいです。
定義
h(m)は満足を表す
0≦a、b
（a，b）の個数は明らかにあります。
f(m)=m 2−h(m)では、
m 2は明らかに積関数です。計算を考慮します。
h(m)の時、見つけにくくないです。
aと
bの異なる素数の間には影響がありません。それぞれの素数を計算して掛け算原理を利用します。
h(m)は積性ですので、知っているならば
h(pk)はどのように計算すれば、上述の転化過程を利用できますか？
O(logn)解を求める
先に考える
nの全因子
m対応の
m 2の和は、上式で直接計算すればいいです。
もう少し考えてみます
h(m)は、明らかに
aと
b値を取る範囲は、
0≦a、b
考慮する
m=pkの場合、令
a=pta⋅ラ、b=ptb⋅rbは、
ラ≦pk−ta且（ラ，p）=1，
rb≦pk−tbであり、（rb，p）＝1である。実は、固定したら
たと
tb
（a，b）の個数は直接計算できます。
ϕ（pk−ta）⋅ϕ（pk−tb）
今求めているのは
h(m)=h(pk)=Σta=0 kΣtb=0 k[ta+tb≧k]⋅ϕ（pk−ta）⋅ϕ（pk−tb）=Σta=0 kΣtb=0 k[ta+tb≦k]⋅ϕ（pta）⋅ϕ(ptb)=Σi=0 kΣj=0 iϕ（pj）⋅ϕ(pk−j)=1＋Σi=1 k(i＋1)pi−2 ipi−1＋(i−1)pi−2=(k＋1)pk−1
さらに一歩進んで
Σki=0 h(pi)=(k+1)pk。
前処理ができます。
O(n−−−√)以内の素数、一回だけ
O(logn)答えを計算します。
コード:
#include <cstdio>
typedef unsigned long long ULL;
const int maxn = 32000;
int tot, prime[maxn], t, n;
bool vis[maxn];
ULL ans1, ans2;
int main()
{
for(int i = 2; i < maxn; ++i)
{
if(!vis[i])
prime[tot++] = i;
for(int j = 0, o; j < tot && (o = i * prime[j]) < maxn; ++j)
{
vis[o] = 1;
if(i % prime[j] == 0)
break;
}
}
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
ans1 = ans2 = 1;
for(int i = 0; i < tot && prime[i] * prime[i] <= n; ++i)
if(n % prime[i] == 0)
{
int cnt = 0, tmp = 1;
ULL sum = 1;
for( ; n % prime[i] == 0; n /= prime[i], ++cnt);
for(int j = 1; j <= cnt; ++j)
{
tmp *= prime[i];
sum += (ULL)tmp * tmp;
}
ans1 *= sum;
ans2 *= tmp * (cnt + 1ULL);
}
if(n > 1)
{
ans1 *= (ULL)n * n + 1;
ans2 *= n * 2ULL;
}
printf("%llu
", ans1 - ans2);
}
return 0;
}