本题我们最终推得的式子是这样的

$\sum_{T\mid N}\biggl\lfloor\dfrac{a}{T}\biggl\rfloor\sum_{d\mid T}\biggl\lfloor\dfrac{bd}{N}\biggl\rfloor\mu(\dfrac{T}{d})$

由于 $\mu$ 仅在 Square Free Number 处有值，所以可以先处理 $T$ 的质因子，然后在搜 $T$ 的无平方因子，这样做是 $O(T(d(N^2)))$ 的。

但是由于本题是 Min25 精心打造的数据，因此这种方法会 T 飞，SPOJ 原题时限只有 6s。

（在极限数据下该程序运算次数超过了 $3e9$）

然后我看到本题有一个 快速莫比乌斯变换 的标签，但是本题似乎不能使用快速莫比乌斯变换。

因为 N 可能不是无平方因子数。

那么，这题该怎么做呢，上述暴力做法还可以优化吗？

这里放上我的代码。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll Maxn=1e5+7,Mod=1e9;
ll T,Np,a,b;
ll cntd,cntp;
pair<int,int>divs[Maxn];
int prm[Maxn];
ll res,ans;

inline void Get(ll s,int p,ll g,ll T){
	
	int mu=g&1?-1:1;
	ll d=T/s;
	if((__int128)d*b<Np) return ; 
	d=(__int128)d*b/Np%Mod;
	res=(res+Mod+mu*d%Mod)%Mod;
	for(int i=p;i<=cntp;++i) Get(s*prm[i],i+1,g+1,T);
}
inline void DFS(ll s,int p){
	res=0;
	Get(1,1,0,s);
	ll a1=(a/s)%Mod;a1=a1*res%Mod;
	ans=(ans+a1);
	while(ans>=Mod)ans-=(ans>=Mod)?Mod:0; 
	for(int i=p;i<=cntd;++i){
		prm[++cntp]=divs[i].first;
		for(ll j=1,pk=divs[i].first;j<=divs[i].second;++j,pk*=divs[i].first) DFS(s*pk,i+1);
		--cntp;
	}
}

int main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld%lld",&Np,&a,&b);
		ll N=Np;ans=0;
		cntd=0;
		for(register int i=2;i<=1e5;++i){
			if(!(N%i)){
				int cnt=0;
				while(!(N%i)) ++cnt,N/=i;
				divs[++cntd]=make_pair(i,cnt);
			}
		}
		DFS(1,1);
		printf("%lld",ans);
		puts("");
	}
	return 0;
}
/*
2
1000000000000000000 100000000000 100000000000
14299762385778870 112999822 28773321122
*/