Golang版 YY的GCD(莫比乌斯反演)

本文主要是介绍Golang版 YY的GCD(莫比乌斯反演)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

学会一种语言最好的办法就是拿它写一道算法题{

鉴于sort和stl实现不了，就选取了莫比乌斯反演的题来实现

golang语法还是挺臭屁的，初学者可能会引起强烈不适，但是大的上面难度还是很低的，这一番操作go也熟悉了不少

package mainimport "fmt"func Min(x, y int) int {if x < y {return x}return y
}
func Max(x, y int) int{if x > y {return x}return y
}
const limit int = 10000005;
var n int;
var num[10000005] int;
var phi[10000005] int;
var miu[10000005] int;
var sum[10000005] int64;
var prime[10000005] int;
var tot int;
func Memset(){for i := 0 ; i < 10000005; i++{num[i] = 1;phi[i] = 0;sum[i] = 0;miu[i] = 0;}
}//全清空
func Ssss(){Memset();tot = 0;num[1] = 0;num[0] = 0;miu[1] = 1;for i := 2 ;i < 10000005 ; i++{if num[i] != 0{tot++;prime[tot] =i;miu[i] = -1;}for j := 1; j <= tot && prime[j] * i < 10000005 ;j++{num[prime[j] * i] = 0;if i % prime[j] == 0{miu[i * prime[j]] = 0;break;}else{miu[i * prime[j]] = -1 * miu[i];//莫比乌斯函数}}}for i := 1 ; i <= tot; i++{for j := prime[i] ; j < 10000005 ; j += prime[i]{sum[j] += int64(miu[j / prime[i]]);//几个平方因子}}for i := 1; i < 10000005 ;i++{sum[i] += sum[i-1];//前缀和}
}
var m int;
func Calc1()int64{var ans int64 = 0;var r int;for l := 1 ; l <= Min(n,m);l = r + 1 {//值域分块var t = n;var s = m;r = Min(t / (t / l), s / (s / l));ans = ans + (int64(sum[r] - sum[l - 1]) * int64(int64(t / l) * int64(s / l)));//fmt.Printf("%d\n",(sum[r] - sum[l - 1]) * (int64(t / l) * int64(s / l)));}return ans;
}
func main() {Ssss();var kase int;fmt.Scanf("%d",&kase);for i := 1; i<=kase;i++{fmt.Scanf("%d%d",&n,&m);fmt.Println(Calc1());}
}