【BZOJ】2820：YYのGCD（モビルウス）

http://www.lydsy.com/JudgeOnline/problem.php?id=2820
この問題はとてもすばらしいです
以下ではデフォルトn＜m
まずbzoj 1101の推理によって、私達は一つの数dに対して得やすいです。
$\sum_｛1<=d<=n'}\mu（d）\times\lflover\frac{n'}{d}\r floor\times \lflor\frac{m'}\r floverでは、n'=\lflor\frac{n}\r flash、m'=\lflor\flash{m}{k}\r flash'$
ですから、この問題は簡単に手に入ります。
$\sum_{pは素数}{n} \sum_｛1<=d==n/p]\mu（d）\times\lflor\frac｛n/p｝｛d｝\r floor\times \lflor\frac｛m/p｝｛d｝\r flor$
下の境界を除いて結合律がありますから（証明書が必要です。up：lflor\frac｛lflor｝fraac｛a｝｛b｝\r flor｝｛r flar=\lflor｛a｝\r flook｝で、このようなsbのものはまだ話していますか？適当な数の本はp=上に設定します。
$\sum_{pは素数}{n} \sum_｛1<=d==n/p]\mu（d）\times\lflor\frac｛n｝｛T｝\r floor\times \lflor\frac｛m｝{T}\r flor$
問題をエニュメレート・Tに変換します。（$T=1ドルを考慮しても大丈夫です。最終的には計上されませんので）、
$\sum_{T=1}{n}\sum_｛begin｛subarray｝{c}p\le n\かつp|T\であり、pは素数\end｛subarray｝\mu（\frac{T}\times\lflover\flar{n}である。 \lflor\frac{m}{T} \r flor$
簡略化して得る
$\sum_{T=1}^{n}\lflor\frac{n}{T}\r flover\times \lflor\frac{m}{T} \rflor \sum_｛begin｛subarray｝{c}p\le n\しかもp|T\で、pは素数\end{subarray}である。 \mu（\frac{T}{p}$
設定$g[x]=\sum_｛begin｛subarray｝{c}p\le n\しかもp|x\\で、pは素数\end{subarray}である。 \mu（\frac{x}{p}$
では、元の形になります
$\sum_{T=1}^{n} \lflor\frac{n}\r\times \lflor\frac{m}{T} \rflor\times g[T]$
綺麗な公式ですね。
g[x]の計算はどうすればいいかを考えます。また、$pが素数またはp mid T$でない場合は、$g[x]=0
私たちは$g[x]$を線形ふるいの時に前処理できますか？x=k\times p、pが質数$の場合、取得できます。
$g[k p]=\begin{cases}\mu(k)&p 124 kの時\\mu(k)-g[k]&p mid kの時\\end{cases}$
まず定義に基づいて、この時
$g[kp]=\sum_{begin}{subarray}{c}p'\le n\\しかもp'kp\しかもp'は素数\end{subarray}である。 \mu（\frac{kp}{p'）$
なぜですか
まず$p 124 kを考慮すると、$kp$質因子が$p$の指数>=2があります。
1、$p'=p$であれば、約束をしたら$mu(k)$が残ります。
2、$p'eq p$、p$の素数>=2は、モビルウス関数の定義によると、0です。
したがって$式1+式2=\mu(k)$
p mid kドルを考慮すると、$kp$品質因子が$p$の指数=1です。
1、$p'=p$であれば、予約後は同じ$
2、$p'eq p$の場合は、$mu$は積関数であり、$pと\frac{k}{p'}$が互質であれば、$mu(p)\mu\left（\frac{k}\right）$を得て和式を提案する。ドル\mu(p)=-1ドルで、和式内の和がちょうど$g[k]$の定義なので、この場合の個数は$g[k]です。
したがって、$式1+式2=-g[k]$
そして1101と同じやり方でブロックを分けて乗ります。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)



const int N=10000005;

int p[N], cnt, np[N], mu[N], g[N], sum[N];

void init() {

	mu[1]=1;

	for2(i, 2, N) {

		if(!np[i]) p[++cnt]=i, mu[i]=-1, g[i]=1;

		for1(j, 1, cnt) {

			int t=p[j]*i; if(t>=N) break;

			np[t]=1;

			if(i%p[j]==0) { mu[t]=0; g[t]=mu[i]; break; }

			mu[t]=-mu[i]; g[t]=mu[i]-g[i];

		}

	}

	for2(i, 1, N) sum[i]=sum[i-1]+g[i];

}



int main() {

	int t=getint(); init();

	while(t--) {

		int n=getint(), m=getint();

		ll ans=0; if(n>m) swap(n, m);

		int pos;

		for(int i=1; i<=n; i=pos+1) {

			pos=min(n/(n/i), m/(m/i));

			ans+=(ll)(sum[pos]-sum[i-1])*(n/i)*(m/i);

		}

		printf("%lld
", ans);

	}

	return 0;

}

　　
 
 
 
Description
神犇YYは数論を虐待して馬鹿にします。×kAcは問題を出しました
N，Mを与えて、1<=x==Nを求めて、1<=y==Mしかもgcd(x，y)を素数の(x，y)にしてどれだけのペアがありますか？
kAcというバカ×きっとできません。そこで教えてもらいに来ました。
複数グループ入力
Input
最初の行の整数Tは、データのグループ数を表します。
次のT行は、行に対して正の整数が二つあり、N、Mを表します。
Output
T行、各行の整数は第iグループのデータの結果を表しています。
Sample Input
2
10
100
Sample Output
30
2791
HINT
 
T=100000 N、M<=100000万円
 
ソurce