当前位置:网站首页>Original title GCD convolution problem and solution

Original title GCD convolution problem and solution

2020-12-06 15:49:59 sun123zxy

It's a competition 、 Answer key 、 Both the program and the data generator are attached to git@github.com:sun123zxy/gcdconv.git On .

Problem

GCD Convolution (gcdconv.cpp/.in/.out) (1s,512MB)

Description

Define a new convolution —— GCD Convolution , It accepts two lengths of \(n\) Sequence \(f,g\) , According to the following formula, the generation length is \(n\) Sequence \(h\)

\[h_k = \sum_{\gcd(i,j) = k} f_i g_j \]

Now given the sequence \(f,g\) , Seek each other \(h_i\) Yes \(998244353\) The value after taking the mold .

Input

Enter a positive integer in the first line \(n\) , Express \(f,g\) The length of .

Second line input \(n\) It's an integer \(f_i\) .

In the third line, enter \(n\) It's an integer \(g_i\) .

Output

To reduce the output , Just output 1 It's an integer , Means each \(h_i\) Yes \(998244353\) The XOR after taking the mold and .

Sample 1

Sample 1 Input

3
5 1 4
2 3 3

Sample 1 Output

78

Sample 1 Explanation

\[\begin{aligned} h_1 &= f_1 ( g_1 + g_2 + g_3 ) + g_1 (f_2 + f_3) + f_2 g_3 + f_3 g_2 = 65 \\ h_2 &= f_2 g_2 = 3 \\ h_3 &= f_3 g_3 = 12 \end{aligned} \]

\[65 \oplus 3 \oplus 12 = 78 \]

Sample 2

Sample 2 Input

4
7 1 8 0
6 2 9 1

Sample 2 Output

158

Sample 2 Explanation

\[\begin{aligned} h_1 &= 213 \\ h_2 &= 3 \\ h_3 &= 72 \\ h_4 &= 0 \end{aligned} \]

\[213 \oplus 3 \oplus 72 \oplus 0 = 158 \]

Sample 3

see sample Under the table of contents gcdconv3.in/.ans .

Constraints

Yes 20% The data of ,\(1 \le n \le 2000\) .

Yes 100% The data of , \(1 \le n \le 4 \times 10^5\) , \(0 \le f_i, g_i \le 998244352\) .

Hints

The time limit is std Of 1.5 About times .std There's no card , The data has a certain gradient , Please feel free to eat .

Source

sun123zxy

???

  • Examples 2 More violent .

The mark says

Default such as \(n,d,i,j,k\) The maximum value of the subscript variable is the length of the sequence given in the title , And replace the sequence with a number theoretic function to express .

Pay attention to the solution to this question \(n\) It's usually a variable , And the length of the sequence defined in the title \(n\) Different .

in addition , use \(\circ\) representative \(\gcd\) Convolution , namely

\[h(n) = (f \circ g)(n) = \sum_{\gcd(i,j) = n} f(i) g(j) \]

Solution

We follow the fast Fourier transform (FFT)、 Fast Mobius transformation (FMT) To solve this problem by solving convolution —— Construct a transformation to satisfy the convolution theorem :

\[\hat f(n) \hat g(n) = \widehat {(f \circ g)}(n) \]

\(\hat f\) That is, for functions \(f\) The function obtained by this transformation .

Through some keen intuition , We can feel \(\gcd\) It has something to do with enumeration divisors or multiples .

It's easy to think of constructing a transformation , be called “ Multiples and transformations ”:

\[\hat f(n) = \sum_{n|d} f(d) \]

According to Mobius inversion, the inverse transformation is obtained

\[f(n) = \sum_{n|d} \mu(\frac n d) \hat f(d) \]

( This is actually another form of the standard Mobius inversion , See the later [Further Thoughts](#Further Thoughts) )

This transformation is right \(\gcd\) Convolution satisfies the convolution theorem , Prove the following .

First , Write \(\gcd\) Convolution

\[h(k) = (f \circ g)(k) = \sum_{i,j} [\gcd(i,j)=k] f(i) g(j) \]

Double and transform left and right :

\[\begin{aligned} \hat h(n) &= \sum_{n|k} \sum_{i,j} [\gcd(i,j)=k] f(i) g(j) \\ &= \sum_{i,j} \left( \sum_{n|k} [\gcd(i,j)=k] \right) f(i) g(j) \quad \\ &= \sum_{i,j} [n|i][n|j] f(i) g(j) \quad \\ &= \sum_{n|i} f(i) \sum_{n|j} g(j) \quad \\ &= \hat f(n) \hat g(n) \end{aligned} \]

Obtain evidence . The core of the above proof lies in \(\sum_{n|k} [\gcd(i,j)=k] = [n|i] [n|j]\) .

therefore , First pair \(f,g\) Do multiples and transformations , And then directly \(O(n)\) Point value multiplication , And then invert it back , You can get \(f \circ g\) .

So the rest of the problem is how to quickly do multiple sum transformation and its inverse transformation . It's very simple Of , Just direct violence . The complexity is \(O(n H(n))\) , The harmonic progression \(H(n)= \sum_{k=1}^{n} \frac 1 k\) , Yes \(\lim_{n \to \infty} H(n) = \ln(n) + c\) . Euler constant \(c \approx 0.57721566490153286060651209\) .

It can be called “ Fast multiples and transformations ”.

The total time complexity is about \(O(n \ln n)\) .

Code

/*
gcd Convolution  (gcdconv) std
by sun123zxy 
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;

ll Rd(){
	ll ans=0;bool fh=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-') fh=1; c=getchar();}
	while(c>='0'&&c<='9') ans=ans*10+c-'0',c=getchar();
	if(fh) ans=-ans;
	return ans;
}

const ll MOD=998244353;
#define _ %MOD
ll PMod(ll x){
	if(x<0) return x+MOD;
	else if(x>=MOD) return x-MOD;
	else return x;
}

const ll MXN=5E5+5;
ll P[MXN],mu[MXN];ll pN;
bool notP[MXN];
void LinearSieve(ll n){
	notP[1]=1;for(ll i=2;i<=n;i++) notP[i]=0;
	P[1]=0;mu[1]=1;
	pN=0;
	for(ll i=2;i<=n;i++){
		if(!notP[i]){
			P[++pN]=i;
			mu[i]=-1;
		}
		for(ll j=1;i*P[j]<=n;j++){
			notP[i*P[j]]=1;
			if(i%P[j]==0){
				mu[i*P[j]]=0;
				break;
			}
			mu[i*P[j]]=mu[i]*mu[P[j]];
		}
	}
}

class Poly{public:
	ll& operator [] (ll idx){return cof[idx];}
	ll n;vector<ll> cof;
	Poly(){}
	Poly(ll n){Resize(n);}
	void Resize(ll n){
		this->n = n;
		cof.resize(n+1,0);
	}
};
namespace PC{//PolyCalc
	void FMT(Poly& A,ll typ){
		ll n=A.n;
		Poly B(n);
		for(ll i=1;i<=n;i++){
			for(ll j=1;i*j<=n;j++){
				ll t=A[i*j];if(typ==-1) t=t*mu[j]_;
				B[i]=PMod(B[i]+t);
			}
		}
		A=B;
	}
	Poly GcdConv(Poly A,Poly B){
		ll n=min(A.n,B.n); 
		Poly C(n);
		FMT(A,1);FMT(B,1);
		for(ll i=1;i<=n;i++) C[i]=A[i]*B[i]_;
		FMT(C,-1);
		return C;
	}
}

ll N;

int main(){
	freopen("gcdconv.in","r",stdin);
	freopen("gcdconv_std.out","w",stdout);
	N=Rd();
	LinearSieve(N);
	Poly A(N),B(N);
	for(ll i=1;i<=N;i++) A[i]=Rd();
	for(ll i=1;i<=N;i++) B[i]=Rd();
	Poly C=PC::GcdConv(A,B);
	ll ans=0;
	for(ll i=1;i<=N;i++) ans^=C[i];
	printf("%lld",ans);
	return 0;
}

Further Thoughts

This problem uses a kind of deformation of Mobius inversion

\[g(n) = \sum_{n|d} f(n) \iff f(d) = \sum_{n|d} \mu(\frac n d) g(d) \]

The original Mobius inversion looks like this

\[g(n) = \sum_{d|n} f(n) \iff f(d) = \sum_{d|n} \mu(\frac n d) g(d) \]

If you change the title to \(\mathrm{lcm}\) Convolution , namely

\[h_k = \sum_{\mathrm{lcm}(i,j) = k} f_i g_j \]

The original Mobius inversion is used . The corresponding structure is “ Divisors and transformations ” Can solve . And divisors and transformations can be done with “ Fast divisors and transformations ”( It's actually an Ethel ) Realization , Interested students can try .

Further Further Thoughts (update 2020/10/28)

Let's talk about something closer to the essence .

Ordinary convolution ( Polynomial multiplication )、 Set merging / Cross convolution 、 also \(\mathrm{lcm}\) / \(\gcd\) Convolution , How do we solve these three problems ?

The key lies in —— We construct the discrete Fourier transform respectively 、 subset-sum / Supersets and transformations ( Mobius transformation ) And divisor and / Multiplication and transformation to satisfy the convolution theorem .

And what is the commonness of these three transformations ?

They are all generalized inversions with graceful properties on posets .

  • Discrete Fourier transform uses unit root inversion —— Its poset is the less than or equal to relation defined on the set of natural numbers ;
  • subset-sum / Supersets and transformations use the inclusion exclusion principle —— Its poset is the inclusion relation defined on the set ;
  • And divisor and / The multiple sum transformation uses Mobius inversion —— Its poset is an integral division relation defined on the set of natural numbers .

The significance of inversion lies in —— It will be the original “ coefficient ” Turn into “ Point value ”, \(O(n)\) Take it and turn back “ coefficient ” Provides the possibility of . And the reason why these three special inversions are beautiful , It's because we found their “ Fast (Fast) ” Change the way , Let's get through this Trick, Save it. \(O(n^2)\) The violent calculation of .

And more importantly —— subset-sum / Superset and transformation and divisor sum / Multiples and transformations are more closely related —— This is also a collection by the author FMT Think of the key to divisors and transformations —— Based on all prime numbers, it can be expanded into a number containing all positive integers “ Prime space ”( Its good definition depends on the unique decomposition theorem of integers ).

Divisors and transformations are “ Prime space ” High dimensional prefixes and , Corresponding “ Set space ” Subsets and transformations in . let me put it another way , Subsets and transformations 、 Divisor and transformation are Mobius transformations in “ Prime space ”、“ Set space ” The concrete embodiment of , They are all high-dimensional prefixes and .

If you understand this , It's not difficult to find the set merge convolution sum \(\mathrm{lcm}\) The commonness of convolution —— They all put numbers in the coordinates of the dimensions of the two input elements \(\max\) The back position ; And set intersection, convolution and \(\gcd\) Convolution is to take \(\min\) .

in summary , With the above knowledge , so to speak \(\gcd\) The discovery of convolution is very natural .

Postscript & thank

Idea It was found in Chinese class ,Solution It was in the math class that followed

Long ago, I felt that FMT And Mobius inversion has some unclear relations , This problem also makes the author understand it more deeply .

As a matter of fact, there are some big men who have been right about \(\mathrm{lcm}\) / \(\gcd\) Convolution expansion has been studied .Google It can be found that there are discussions on this aspect in foreign mathematics communities , At the latest 2013 year arXiv There are papers on its nature ( The writer is dull , It's really hard to understand , If you are interested, you can directly Google "GCD Convolution" understand ). It's a pity that it's so natural and wonderful \(\gcd\) Convolution , Unexpectedly, it was not introduced into China with the paper on set power series , Let the author feel some regret .

All in all , This question has a deep study on FFT、FMT The understanding of the principle and the understanding of \(\gcd\) 、 The keen intuition of Mobius inversion , It's a rare number theory problem (

Here is the tactical thank you session .

thank keke The student taught us the set power series .

thank TbYangZ、diong god 、changruinian2020 A few gods .

And you...

——sun123zxy

Sep. 2020 The first draft is finished

Nov. 2020 The last update

版权声明
本文为[sun123zxy]所创,转载请带上原文链接,感谢
https://chowdera.com/2020/12/202012061547554063.html