YY의 GCD
제목의 뜻
∑ni=1∑mj=1(gcd(i,j)==pi)∑i=1n∑j=1m(gcd(i,j)==pi)pi는 질수 pi는 질수
제목 분석:
프리 프로세싱μ(Tp) μ (T p) 접두사 및
제목 링크:
Luogu 2257
Ac 코드:
#include
#include
#include
#define sqr(x) x*x
#define ll long long
const int maxm=10000010;
ll mu[maxm],sum[maxm],f[maxm];
int cnt,prime[maxm];
bool vis[maxm];
void getmu()
{
mu[1]=1,vis[1]=1;
for(int i=2;i<=maxm;i++)
{
if(!vis[i])
{
prime[++cnt]=i;
//printf("%d
",i);
mu[i]=-1;
}
for(int j=1;j<=cnt&&prime[j]*i<=maxm;j++)
{
vis[prime[j]*i]=1;
if(i%prime[j]==0)
{
mu[prime[j]*i]=0;
break;
}
mu[prime[j]*i]=-mu[i];
}
}
for(int i=1;i<=cnt;i++)
for(int j=1;j*prime[i]<=maxm;j++)
f[j*prime[i]]+=mu[j];
for(int i=2;i<=maxm;i++) sum[i]=sum[i-1]+f[i];
}
int main()
{
int q;
scanf("%d",&q);
getmu();
while(q--)
{
ll n,m;
scanf("%lld%lld",&n,&m);
ll ans=0;
int last=0;
for(int i=1;i<=std::min(n,m);i=last+1)
{
last=std::min(n/(n/i),m/(m/i));
ans+=(1ll*(n/i)*1ll*(m/i)*1ll*(sum[last]-sum[i-1]));
}
printf("%lld
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
YY의 GCD∑ni=1∑mj=1(gcd(i,j)==pi)∑i=1n∑j=1m(gcd(i,j)==pi)pi는 질수 pi는 질수 프리 프로세싱μ(Tp) μ (T p) 접두사 및 Luogu 2257...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.