写的 $O(Td(n^2))$ 做法，感觉挺对

#include<bits/stdc++.h>
#define ll long long
#define lll __int128
using namespace std;
const int N=1e5+10,V=1e5,mod=1e9;
int t,cnt,s,ans,prime[N],p[N],c[N],f[N];
bitset<N>mark;
ll n,a,b;
inline void init(){
  int i,j;
  mark.set();
  for(i=2;i<=V;i++){
    if(mark[i])prime[++cnt]=i;
    for(j=1;j<=cnt&&prime[j]*i<=V;j++){
      mark[i*prime[j]]=0;
      if(i%prime[j]==0)break;
	}
  }
  return;
}
int dfs2(int st,ll m,ll d,int fl){
  if(d>b/(n/m))return 0;
  if(st==s+1){
    int res=(b/(n/m)/d)%mod;
    if(fl==-1)res=mod-res;
	return res;
  }
  int res=dfs2(st+1,m,d,fl);
  if(f[st])res=(res+dfs2(st+1,m,d*(ll)p[st],-fl))%mod;
  return res;
}
void dfs(int st,ll m){
  if(st==s+1){
    int res=(ll)((a/m)%mod)*dfs2(1,m,1,1) %mod;
    ans=(ans+res)%mod;
	return;
  }
  int i;ll v=p[st];
  f[st]=0;dfs(st+1,m);
  f[st]=1;
  if(v>a/m)return;
  for(i=1;i<=c[st];i++){
    dfs(st+1,m*v);
	if(v>a/m/(ll)p[st])break;
	v*=(ll)p[st];
  }
  return;
}
int main(){
	scanf("%d",&t);
	int i;
	init();
	while(t--){
	  scanf("%lld %lld %lld",&n,&a,&b);
	  s=0;ll val=n;
	  for(i=1;i<=cnt;i++)
	    if(val%prime[i]==0){
	      s++;p[s]=prime[i];c[s]=0;
	      while(val%(ll)prime[i]==0)val/=(ll)prime[i],c[s]++;
		}
	  dfs(1,1);
	  printf("%d\n",ans);
	  ans=0;
	}
	return 0;
}
/*
1
614889782588491410 1000000000000000000 1000000000000000000
*/