【SDOI 2018旧問題】
8481 ワード
約束:
((i,j))は(gcd(i,j)==1)を表す.
([x])は、対(x)が下向きに整列していることを示します.
まず、次のようなものがあります.
\[d(ijk)=\sum_{u|i}\sum_{v|j}\sum_{w|k}(u,v)(v,w)(w,u)\]
そこでテーマが求めたのは:
\[\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{u|i}\sum_{v|j}\sum_{w|k}(u,v)(v,w)(w,u)\]
次に、ファクタを列挙する必要があります.
\[\sum_{u=1}^A[\dfrac{A}{u}]\sum_{v=1}^B[\dfrac{B}{v}]\sum_{w=1}^C[\dfrac{C}{w}](u,v)(v,w)(w,u)\]
この時にもう一度反転して、得ます:
\[\sum_{u=1}^A[\dfrac{A}{u}]\sum_{v=1}^B[\dfrac{B}{v}]\sum_{w=1}^C[\dfrac{C}{w}]\sum_{d|gcd(u,v)}\mu(d)\sum_{k|gcd(v,w)}\mu(k)\sum_{h|gcd(w,u)}\mu(h)\]
列挙の順序を変えなければなりません
次のようになります.
\[\sum_{d=1}^{min(A,B)}\mu(d)\sum_{k=1}^{min(B,C)}\mu(k)\sum_{h=1}^{min(C,A)}\mu(h)\sum_{u|d\&u|h}^{A}[\dfrac{A}{u}]\sum_{v|d\&v|k}^{B}[\dfrac{B}{v}]\sum_{w|k\&w|h}^{C}[\dfrac{C}{w}]\]
それと同時に二つを取り除くのは醜いから、私たちは(u|lcm(d,h))に変えましょう.
次のようになります.
\[\sum_{d=1}^{min(A,B)}\mu(d)\sum_{k=1}^{min(B,C)}\mu(k)\sum_{h=1}^{min(C,A)}\mu(h)\sum_{u|lcm(d,h)}^{A}[\dfrac{A}{u}]\sum_{v|lcm(d,k)}^{B}[\dfrac{B}{v}]\sum_{w|lcm(k,h)}^{C}[\dfrac{C}{w}]\]
後ろの大きな塊は2つの量と関係があるようだ
(A,lcm(d,h))のような変数
コアの式を書き直してみましょう.
\[\sum_{u|lcm(d,h)}^A[\dfrac{A}{u}]\]
\[=\sum_{u=1}^{\frac{A}{lcm(d,h)}}[\dfrac{A}{u*lcm(d,h)}]\]
我々は、(f(n,x))表示を考慮する.
\[\sum_{i=1}^{\frac{n}{x}}[\dfrac{n}{i*x}]\]
1つの引数に気づきました.
\[[\dfrac{[\frac{n}{x}]}{i}]=[\dfrac{n}{ix}]\]
すると、
\[\sum_{i=1}^{\frac{n}{x}}[\dfrac{n}{i*x}]=\sum_{i=1}^{\frac{n}{x}}[\dfrac{[\frac{n}{x}]}{i}]\]
つまり、
\[\sum_{i=1}^x[\dfrac{x}{i}]\]
だから私たちは(f(x)=sum_を覚えています.{i=1}^x[\dfrac{x}{i}]\)
原題が求めているのは次のとおりです.
\[\sum_{d=1}^{min(A,B)}\mu(d)\sum_{k=1}^{min(B,C)}\mu(k)\sum_{h=1}^{min(C,A)}\mu(h)*f(\dfrac{A}{lcm(d,h)})f(\dfrac{B}{lcm(d,k)})f(\dfrac{C}{lcm(h,k)})\]
どうやら(f(x))は一度に(sqrt x)求められるようです
私たちはもっと速く押すことを考えました.
ある数(ile x)に対して、その(f(x))に対する寄与は(dfrac{x}{i})すなわち(1−x)内の何個の数がその倍数であるかに注目する
したがって(f)の実際の意味は(1−x)内の約数と
これであなたは(nlog n)|O(n))これらの値を押し出すことができます.
もちろんあなたの複雑さは逆転しても(O(n^3log n))のqwqです
我々が求めているのは,実際には秩序が((d,k,h))の答えに寄与していることが分かった.
そこで変換問題のモデルを考えて、図を作ることができます.
2つの点((u,v))の間に1つのエッジを接続することを考慮します.
これは無方向のエッジで、このエッジのエッジ権は(lcm(u,v))、私たちはエッジ(u,v)のエッジ権を(w_{u,v})と覚えています.
すると、1つの秩序ペア((d,k,h))について、2つが異なる場合、この図の3元ループで表すことができるようになります.
三元環((d,k,h))の場合、その答えに寄与するのは、(dlemin(A,B)、klemin(B,C)、hlemin(C,A))のみである.
では、答えに(mu(d)*mu(k)*mu(h)*f(dfrac{A}{w_{d,h})f(dfrac{B}{w_{d,k})f(dfrac{C}{w_{h,k})をもたらします.
この図で3元ループカウントをして答えを統計できるようになりましたqwq
それでも暴力的らしい
この図の枝を切ってみましょう
大量の三元環が答えに寄与していることが分かった(0)
そこで、(mu(x)=0)または(lcm(u,v)>max(A,B,C))の点をすべて削除することができます.
shadowice 1984集積によると、このように切った後、原図の辺は少ないという.
もちろん、暴力建辺の複雑さは(O(n^2))の——(Step(1))
この定義の下で構築されたエッジは,2つの等しくない3元グループが答えに与える寄与を統計するしかないことに気づいた.
私たちは暴力統計を考慮して、毎回1つの点を列挙してその出点とその出点の出点を列挙して、このように複雑度は(O(nm))です——(Step(2))
2つの等しい3つのグループが答えに貢献したことを判断するために、追加の特判を書く必要があります.
2つの等しい3元グループを計算する複雑さは(O(m))であり,3つのすべての等しい複雑さを計算すると(O(n))であることが分かった.
(5000)の点の部分の辺を数えてみると(49528)
もしあなたが2点の間にエッジがあるかどうかを判断するために(map)を書いたら、きっとTが飛んで1点も得られません.
そうでなければ、(log)ではなく単純な非厳格(nm)を持っていれば、(30 pts)の高い点数を得ることができるはずです.
そこで最適化を検討します
(1.)最適化(Step 2)
そこで三元ループカウントのテクニックを出して使うと、複雑さを(msqrt m)に変えることができます.
もちろん三元ループカウント統計は無方向三元ループカウントである
6つの異なる配列を列挙して正確性を確保しなければなりません
これで複雑さを(O(n^2+msqrt m))にすることができます
一発書いて渡してみると驚くべきことに、このやり方はまだ(30)点のようです.
(2.)最適化(Step 1)
私たちは(n^2)の列挙でエッジを構築しないことを考えています.
1つの(gcd=x)を列挙することを考慮すると、(i=kx,j=px)
則(gcd(k,p)==1)
そして(mu(i)e 0,mu(j)e 0)及び((kpx)le max(A,B,C))
この点対((k,p))を列挙すればよい
もちろん、このようなエッジの複雑さは(O(m))ではありません.
でも(O(n^2))よりも速く、しかもずっと速く
近似(O(m))についてのエッジは、列挙(lcm)を考慮し、同時に(mu(lcm)e 0)を考慮し、それを素因数で分解し、可能な(mu(x)e 0)の点を列挙し、各点について因数に関する取または取バイナリによってラベルを外し、バケツを記録し、そのサブセットを列挙すると、そのサブセットとそのサブセット(&)の結果となる.
そこであなたはとても楽しくて自分でこの問題のコードを打つことができると思っています
もちろんvectorを使っていれば本当に過ごせます
さもないとあなたは(T)
コードの中で2つの等しい3元グループの答えへの貢献について、この料理が死ぬ筆者は暴力を書き終わってから2つの最適化を加えたので、彼は辺をつなぐ時にこの状況を処理しなかった.
実際にはエッジをつなぐ過程で処理できるqwqです
ヒント(1:)三元グループを列挙するときに受ける制限が面倒そうな様子(min(A,B),min(B,C),min(C,A))
しかし、実際には管理する必要はありません.統一的に制限を(max(A,B,C))にすればいいのです.
なぜなら(u>min(A,B))では(f(min(A,B)/u)=0)
次は醜くて長いコードです
((i,j))は(gcd(i,j)==1)を表す.
([x])は、対(x)が下向きに整列していることを示します.
まず、次のようなものがあります.
\[d(ijk)=\sum_{u|i}\sum_{v|j}\sum_{w|k}(u,v)(v,w)(w,u)\]
そこでテーマが求めたのは:
\[\sum_{i=1}^A\sum_{j=1}^B\sum_{k=1}^C\sum_{u|i}\sum_{v|j}\sum_{w|k}(u,v)(v,w)(w,u)\]
次に、ファクタを列挙する必要があります.
\[\sum_{u=1}^A[\dfrac{A}{u}]\sum_{v=1}^B[\dfrac{B}{v}]\sum_{w=1}^C[\dfrac{C}{w}](u,v)(v,w)(w,u)\]
この時にもう一度反転して、得ます:
\[\sum_{u=1}^A[\dfrac{A}{u}]\sum_{v=1}^B[\dfrac{B}{v}]\sum_{w=1}^C[\dfrac{C}{w}]\sum_{d|gcd(u,v)}\mu(d)\sum_{k|gcd(v,w)}\mu(k)\sum_{h|gcd(w,u)}\mu(h)\]
列挙の順序を変えなければなりません
次のようになります.
\[\sum_{d=1}^{min(A,B)}\mu(d)\sum_{k=1}^{min(B,C)}\mu(k)\sum_{h=1}^{min(C,A)}\mu(h)\sum_{u|d\&u|h}^{A}[\dfrac{A}{u}]\sum_{v|d\&v|k}^{B}[\dfrac{B}{v}]\sum_{w|k\&w|h}^{C}[\dfrac{C}{w}]\]
それと同時に二つを取り除くのは醜いから、私たちは(u|lcm(d,h))に変えましょう.
次のようになります.
\[\sum_{d=1}^{min(A,B)}\mu(d)\sum_{k=1}^{min(B,C)}\mu(k)\sum_{h=1}^{min(C,A)}\mu(h)\sum_{u|lcm(d,h)}^{A}[\dfrac{A}{u}]\sum_{v|lcm(d,k)}^{B}[\dfrac{B}{v}]\sum_{w|lcm(k,h)}^{C}[\dfrac{C}{w}]\]
後ろの大きな塊は2つの量と関係があるようだ
(A,lcm(d,h))のような変数
コアの式を書き直してみましょう.
\[\sum_{u|lcm(d,h)}^A[\dfrac{A}{u}]\]
\[=\sum_{u=1}^{\frac{A}{lcm(d,h)}}[\dfrac{A}{u*lcm(d,h)}]\]
我々は、(f(n,x))表示を考慮する.
\[\sum_{i=1}^{\frac{n}{x}}[\dfrac{n}{i*x}]\]
1つの引数に気づきました.
\[[\dfrac{[\frac{n}{x}]}{i}]=[\dfrac{n}{ix}]\]
すると、
\[\sum_{i=1}^{\frac{n}{x}}[\dfrac{n}{i*x}]=\sum_{i=1}^{\frac{n}{x}}[\dfrac{[\frac{n}{x}]}{i}]\]
つまり、
\[\sum_{i=1}^x[\dfrac{x}{i}]\]
だから私たちは(f(x)=sum_を覚えています.{i=1}^x[\dfrac{x}{i}]\)
原題が求めているのは次のとおりです.
\[\sum_{d=1}^{min(A,B)}\mu(d)\sum_{k=1}^{min(B,C)}\mu(k)\sum_{h=1}^{min(C,A)}\mu(h)*f(\dfrac{A}{lcm(d,h)})f(\dfrac{B}{lcm(d,k)})f(\dfrac{C}{lcm(h,k)})\]
どうやら(f(x))は一度に(sqrt x)求められるようです
私たちはもっと速く押すことを考えました.
ある数(ile x)に対して、その(f(x))に対する寄与は(dfrac{x}{i})すなわち(1−x)内の何個の数がその倍数であるかに注目する
したがって(f)の実際の意味は(1−x)内の約数と
これであなたは(nlog n)|O(n))これらの値を押し出すことができます.
もちろんあなたの複雑さは逆転しても(O(n^3log n))のqwqです
我々が求めているのは,実際には秩序が((d,k,h))の答えに寄与していることが分かった.
そこで変換問題のモデルを考えて、図を作ることができます.
2つの点((u,v))の間に1つのエッジを接続することを考慮します.
これは無方向のエッジで、このエッジのエッジ権は(lcm(u,v))、私たちはエッジ(u,v)のエッジ権を(w_{u,v})と覚えています.
すると、1つの秩序ペア((d,k,h))について、2つが異なる場合、この図の3元ループで表すことができるようになります.
三元環((d,k,h))の場合、その答えに寄与するのは、(dlemin(A,B)、klemin(B,C)、hlemin(C,A))のみである.
では、答えに(mu(d)*mu(k)*mu(h)*f(dfrac{A}{w_{d,h})f(dfrac{B}{w_{d,k})f(dfrac{C}{w_{h,k})をもたらします.
この図で3元ループカウントをして答えを統計できるようになりましたqwq
それでも暴力的らしい
この図の枝を切ってみましょう
大量の三元環が答えに寄与していることが分かった(0)
そこで、(mu(x)=0)または(lcm(u,v)>max(A,B,C))の点をすべて削除することができます.
shadowice 1984集積によると、このように切った後、原図の辺は少ないという.
もちろん、暴力建辺の複雑さは(O(n^2))の——(Step(1))
この定義の下で構築されたエッジは,2つの等しくない3元グループが答えに与える寄与を統計するしかないことに気づいた.
私たちは暴力統計を考慮して、毎回1つの点を列挙してその出点とその出点の出点を列挙して、このように複雑度は(O(nm))です——(Step(2))
2つの等しい3つのグループが答えに貢献したことを判断するために、追加の特判を書く必要があります.
2つの等しい3元グループを計算する複雑さは(O(m))であり,3つのすべての等しい複雑さを計算すると(O(n))であることが分かった.
(5000)の点の部分の辺を数えてみると(49528)
もしあなたが2点の間にエッジがあるかどうかを判断するために(map)を書いたら、きっとTが飛んで1点も得られません.
そうでなければ、(log)ではなく単純な非厳格(nm)を持っていれば、(30 pts)の高い点数を得ることができるはずです.
そこで最適化を検討します
(1.)最適化(Step 2)
そこで三元ループカウントのテクニックを出して使うと、複雑さを(msqrt m)に変えることができます.
もちろん三元ループカウント統計は無方向三元ループカウントである
6つの異なる配列を列挙して正確性を確保しなければなりません
これで複雑さを(O(n^2+msqrt m))にすることができます
一発書いて渡してみると驚くべきことに、このやり方はまだ(30)点のようです.
(2.)最適化(Step 1)
私たちは(n^2)の列挙でエッジを構築しないことを考えています.
1つの(gcd=x)を列挙することを考慮すると、(i=kx,j=px)
則(gcd(k,p)==1)
そして(mu(i)e 0,mu(j)e 0)及び((kpx)le max(A,B,C))
この点対((k,p))を列挙すればよい
もちろん、このようなエッジの複雑さは(O(m))ではありません.
でも(O(n^2))よりも速く、しかもずっと速く
近似(O(m))についてのエッジは、列挙(lcm)を考慮し、同時に(mu(lcm)e 0)を考慮し、それを素因数で分解し、可能な(mu(x)e 0)の点を列挙し、各点について因数に関する取または取バイナリによってラベルを外し、バケツを記録し、そのサブセットを列挙すると、そのサブセットとそのサブセット(&)の結果となる.
そこであなたはとても楽しくて自分でこの問題のコードを打つことができると思っています
もちろんvectorを使っていれば本当に過ごせます
さもないとあなたは(T)
コードの中で2つの等しい3元グループの答えへの貢献について、この料理が死ぬ筆者は暴力を書き終わってから2つの最適化を加えたので、彼は辺をつなぐ時にこの状況を処理しなかった.
実際にはエッジをつなぐ過程で処理できるqwqです
ヒント(1:)三元グループを列挙するときに受ける制限が面倒そうな様子(min(A,B),min(B,C),min(C,A))
しかし、実際には管理する必要はありません.統一的に制限を(max(A,B,C))にすればいいのです.
なぜなら(u>min(A,B))では(f(min(A,B)/u)=0)
次は醜くて長いコードです
#include
using namespace std;
#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )
#define re register
#define int long long
int read() {
char cc = getchar(); int cn = 0, flus = 1;
while(cc < '0' || cc > '9') { if( cc == '-' ) flus = -flus; cc = getchar(); }
while(cc >= '0' && cc <= '9') cn = cn * 10 + cc - '0', cc = getchar();
return cn * flus;
}
const int N = 100000 + 500 ;
const int P = 1e9 + 7 ;
int A, B, C, f[N], u[N], p[N], d[N], r[N], deg[N], vis[N], book[N], cnt, tot, top ;
bool isp[N] ;
struct E { int to, w ; };
struct node { int u, v, w ; } e[N * 10];
vector mp[N] ;
inline void init() {
isp[1] = 1, u[1] = 1, r[++ tot] = 1, book[1] = tot ;
for( re int i = 2; i <= N - 5; ++ i ) {
if( !isp[i] ) p[++ top] = i, u[i] = -1 ;
for( re int j = 1; j <= top && i * p[j] <= N - 5; ++ j ) {
isp[i * p[j]] = 1 ;
if( i % p[j] == 0 ) continue ;
u[i * p[j]] = - u[i] ;
}
if( u[i] != 0 ) r[++ tot] = i, book[i] = tot ;
}
for( re int i = 1; i <= N - 5; ++ i ) {
for( re int j = i; j <= N - 5; j += i ) ++ d[j] ;
f[i] = ( f[i - 1] + d[i] ) % P ;
}
}
inline int gcd( int x, int y ) {
if( x == 0 ) return y ;
return gcd( y % x, x ) ;
}
signed main()
{
int T = read() ; init() ;
while( T-- ) {
memset( mp, 0, sizeof(mp) ), memset( deg, 0, sizeof(deg) ) ;
A = read(), B = read(), C = read(), cnt = 0 ;
int Ans = 0, D = 0 ; D = max( A, max( B, C ) ) ;
//
for( re int g = 1; r[g] <= D; ++ g ) {
for( re int i = 1; r[i] * r[g] <= D; ++ i ) {
if( !u[r[i] * r[g]] ) continue ;
for( re int j = i + 1; j <= tot && r[i] * r[j] * r[g] <= D; ++ j ) {
if( !u[r[j] * r[g]] || gcd( r[i], r[j] ) != 1 ) continue ;
int u = book[r[i] * r[g]], v = book[r[j] * r[g]], w = r[i] * r[j] * r[g] ;
++ deg[u], ++ deg[v], e[++ cnt] = (node){ u, v, w } ;
mp[u].push_back((E){v, w}), mp[v].push_back((E){u, w}) ;
}
}
}
//
int rD = min( A, min( B, C ) ) ;
for( re int i = 1; r[i] <= min( A, B ); ++ i ) {
int siz = mp[i].size() - 1 ;
rep( j, 0, siz ) {
int u1 = mp[i][j].to ;
Ans += u[r[i]] * u[r[u1]] * u[r[u1]] * f[A / mp[i][j].w] * f[B / mp[i][j].w] * f[C / r[u1]] ;
Ans += u[r[i]] * u[r[i]] * u[r[u1]] * f[A / r[i]] * f[B / mp[i][j].w] * f[C / mp[i][j].w] ;
Ans += u[r[i]] * u[r[i]] * u[r[u1]] * f[A / mp[i][j].w] * f[B / r[i]] * f[C / mp[i][j].w] ;
}
}
//
for( re int i = 1; r[i] <= rD; ++ i ) Ans += u[r[i]] * u[r[i]] * u[r[i]] * f[A / r[i]] * f[B / r[i]] * f[C / r[i]] ;
//
memset( mp, 0, sizeof(mp) ) ;
for( re int i = 1; i <= cnt; ++ i )
if( deg[e[i].u] >= deg[e[i].v] ) mp[e[i].u].push_back((E){ e[i].v, e[i].w }) ;
else mp[e[i].v].push_back((E){ e[i].u, e[i].w }) ;
for( re int i = 1; r[i] <= D; ++ i ) {
int siz = mp[i].size() - 1 ;
rep( j, 0, siz ) vis[mp[i][j].to] = mp[i][j].w ;
rep( j, 0, siz ) {
int u1 = mp[i][j].to, siz2 = mp[u1].size() - 1 ;
rep( k, 0, siz2 ) {
int v = mp[u1][k].to ;
if( !vis[v] ) continue ;
int muu = u[r[i]] * u[r[u1]] * u[r[v]], b = mp[i][j].w, c = mp[u1][k].w, a = vis[v] ;
int rc = f[A / a] * ( f[B / b] * f[C / c] + f[B / c] * f[C / b] )
+ f[A / b] * ( f[B / a] * f[C / c] + f[B / c] * f[C / a] )
+ f[A / c] * ( f[B / a] * f[C / b] + f[ B / b ] * f[C / a] ) ;
Ans += muu * rc ;
}
}
rep( j, 0, siz ) vis[mp[i][j].to] = 0 ;
}
printf("%d
", Ans % P ) ;
}
return 0;
}