大理建网站,飞鸽网站建设,网站制作域名是免费的吗,网站建设下单源码题意: 给定a#xff0c;b#xff0c;d求gcd(x,y)d的对数(1xa,1yb) 思路#xff1a;按照套路来先设f(n)为gcd(x,y)n的对数,g(n)表示为 n | gcd(x,y)的对数,则g(n)∑n|df(d)a/n*b/n f(n)∑n|dg(d)*mu(d/n),令td/n则f(n)∑t1g(t*n)*mu(t)#xff0c;然后求f(d…题意: 给定abd求gcd(x,y)d的对数(1xa,1yb) 思路按照套路来先设f(n)为gcd(x,y)n的对数,g(n)表示为 n | gcd(x,y)的对数,则g(n)∑n|df(d)a/n*b/n f(n)∑n|dg(d)*mu(d/n),令td/n则f(n)∑t1g(t*n)*mu(t)然后求f(d)就行了 #includeiostream
#includealgorithm
#includestring.h
#includestring
#includevector
#includecstdio
#includequeue
#includemap
#includeset
#includemath.h
using namespace std;
const int inf0x3f3f3f3f;
const int maxn1e55;
typedef long long ll;
int dir[4][2]{-1,0,1,0,0,-1,0,1};
int prime[maxn/10];
int tot;
int mu[maxn];
int sum[maxn];
int vis[maxn];
void table(){memset(vis,0,sizeof(vis));memset(sum,0,sizeof(sum));memset(mu,0,sizeof(mu));tot0;mu[1]1;vis[0]vis[1]1;sum[1]1;for(int i2;imaxn;i){if(!vis[i]){prime[tot]i;mu[i]-1;}sum[i]sum[i-1]mu[i];for(int j0;jtoti*prime[j]maxn;j){vis[i*prime[j]]1;if(i%prime[j]){mu[i*prime[j]]-mu[i];}else break;}}
}
int main(){ll t;ios::sync_with_stdio(false);table();cint;while(t--){ll a,b,d;cinabd;a/d;b/d;ll limitmin(a,b);ll ans0;for(ll x1,y;xlimit;){//coutxendl;ymin(a/(a/x),b/(b/x));ans(a/x)*(b/x)*(sum[y]-sum[x-1]);xy1;}coutansendl;}
} 转载于:https://www.cnblogs.com/azznaz/p/10727402.html
