yukicoder : No.2249 GCDistance

これはすんなり。
https://yukicoder.me/problems/no/2249

問題

クエリとして正整数Nが与えられる。
1～NのラベルがついたN頂点の無向グラフを考える。
ラベルxの点とyの点の間には、長さGCD(x,y)の辺が張られているとする。
全頂点対における最短距離の総和を求めよ。

解法

f(n) := ラベルnの頂点から、ラベルn未満の点への最短距離の総和
とすると、f(n)の累積和を事前に求めれば、各クエリにO(1)で答えられる。

ラベルx,yの点の最短距離は、互いに素なら1、そうでないならラベル1の点を経由することで2となる。
よって、トーシェント関数を使い f(n)=2(n-1)-φ(n) と書ける。
あとはφ(n)を各nについてまとめて計算しよう。

int T;
int t[10101010];
ll S[10101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=10000000;i++) {
		t[i]=i;
	}
		
	for(i=2;i<=10000000;i++) {
		if(t[i]==i) {
			for(j=i;j<=10000000;j+=i) {
				t[j]=t[j]/i*(i-1);
			}
		}
		S[i]+=S[i-1]+(2*i-2-t[i]);
	}
	
	cin>>T;
	while(T--) {
		cin>>x;
		cout<<S[x]<<endl;
	}
}

まとめ

10^7とかの配列を取ると、ちょっとメモリ消費が心配になってくる。