luogu \ # 2522 Problem b (모 비 우 스 재연) (HAOI 2011)

수학
제 시 된 n 개 질문 에 대해 매번 몇 개의 수 대 (x, y) 를 구 할 때마다 a ≤ x ≤ b, c ≤ y ≤ d 를 만족 시 키 고 gcd (x, y) = k, gcd (x, y) 함 수 는 x 와 y 의 최대 공약수 이다.a,b,c,d,k<=50000
g (a, b, c, d) 를 제목 으로 요구 하고 f (m, n) 를 만족 시 키 기 위해 1 ≤ x ≤ m, 1 ≤ y ≤ n, 그리고 gcd (x, y) = k 의 수 대 개 수 를 기록 하고 F (m, n) 를 만족 시 키 기 위해 1 ≤ x ≤ m, 1 ≤ y ≤ n, 그리고 gcd (x, y)% k = 0 의 수 대 개 수 를 기록한다.우선 g (a, b, c, d) = f (b, d) - f (a - 1, d) - f (b, c - 1) + f (a - 1, c - 1), f (n, m) 와 F (n, m) 는 모 비 우 스 의 반 연 을 만족 시 키 는 것 을 발견 하기 어렵 지 않다.분명히 F (n, m) = [n / k] * 8727 ° [m / k] 는 f (n, m) = ＞ min (n / k, m / k) i = 1F (n / i, m / i) * 8727 ° 가 있다.μ(i) 그러나 이렇게 되면 복잡 도 는 O (n2) 이 고 요 구 를 만족 시 키 지 못 한다. n / i 는 n √ 가지 수치 만 있다 는 것 을 알 아차 리 지 못 한다. 우 리 는 미리 처리한다.μ(i) 접두사

#include
#include
#include
#include
#define N 50050
using namespace std;
typedef long long ll;
int u[N],vis[N],p[N],top=0,t,a,b,c,d,k;
ll ans;
ll solve(int n,int m)
{
    n/=k,m/=k;
    ll ret=0,last=0;
    if (n>m) swap(n,m);
    for (int i=1;i<=n;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ret+=(ll)(n/i)*(m/i)*(u[last]-u[i-1]);
    }
    return ret;
}
int main()
{
    scanf("%d",&t),memset(vis,0,sizeof(vis)),u[1]=1;
    for (int i=2;i<=N-50;i++)
    {
        if (!vis[i]) {p[++top]=i,u[i]=-1;}
        for (int j=1;j<=top&&i*p[j]<=N-50;j++)
        {
            vis[i*p[j]]=1;
            if (i%p[j]) u[i*p[j]]=u[i]*u[p[j]];else break;
        }
    }
    for (int i=2;i<=N-50;i++) u[i]+=u[i-1];
    while (t--)
    {
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k),ans=solve(b,d)-solve(a-1,d)-solve(c-1,b)+solve(a-1,c-1);
        printf("%lld
",ans);
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Coq에서 증명된 이중 부정 주위의 증명

이중 부정 가져오기 이중 부정 해소를 증명할 수 없지만 삼중 부정 해소를 증명할 수 있다 이중 부정 해소의 이중 부정 이중 부정 해소와 배중률 동치 고전 이론을 얻으려면 직관주의 이론에 어느 것을 넣어도 된다는 것이...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

luogu \ # 2522 Problem b (모 비 우 스 재연) (HAOI 2011)

좋은 웹페이지 즐겨찾기