오로라 함수 와 최대 공약수 의 응용

                 :     N(N    ),   1~N      X  X  GCD(X,N)>=M,        .

분석: 이것 은 통계 유형의 문제 입 니 다. 비교적 쉽게 생각 할 수 있 는 해법 은 GCD (X, N) 의 값 을 매 거 하 는 것 입 니 다. 매 거 진 GCD (X, N) 의 값 d 에 대해 N = p * d, X = q * d 라면 GCD (X, N) = d 는 반드시 p, q 의 호환성 이 있 고 X < = N 이 있 으 면 q < = p 입 니 다. 이런 q 의 개 수 는 p 의 오로라 함수 에 대응 합 니 다. 즉 GCD (X, N) = d 의 X 개 수 는 N / d 의 오로라 함수 값 을 만족 시 킵 니 다.
응용 1: N 과 M 을 주 고 몇 개의 X 가 1 < = X < = N 을 만족 시 키 는 지, 그리고 (X, N) > = M 을 만족 시 키 는 지 구하 십시오.
문제 풀이 방향: 이 문제 에 대해 서 는 문제 의 뜻 을 만족 시 키 는 X 의 개수 만 구하 기 때문에 최대 공약수 d 를 매 거 할 수 있 고 gcd (X, N) = d 를 만족 시 키 는 X 의 개 수 는 N / d 의 오로라 함수 입 니 다. 이 d 에 대응 하 는 N / d 의 오로라 함수 값 을 구 하면 됩 니 다.

       LL res=0,i;
        for(i=1;i*i<=n;i++)
        {
            if(n%i==0)
            {
                if(i>=m)
                    res+=euler(n/i)*i;
                if(i*i!=n&&n/i>=m)
                    res+=euler(i)*(n/i);
            }
        }
        printf("%lld
",res);

응용 2: 숫자 N 을 드 리 겠 습 니 다. 1 ~ N 사이 에 x 를 찾 아 gcd (x, N) > = M 을 만족 시 킬 수 있 도록 gcd (x, N) 의 합 을 찾 을 수 있 습 니 다. 분석: 이 문 제 는 gcd (X, N) 의 합 을 요구 합 니 다. 지난 문 제 는 문제 의 뜻 을 만족 시 키 는 개 수 를 구 했 기 때문에 지난 응용 을 바탕 으로 최대 공약수 만 곱 하면 최종 답 입 니 다.

        LL res=0,i;
        for(i=1;i*i<=n;i++)
        {
            if(n%i==0)
            {
                if(i>=m)
                    res+=euler(n/i)*i;
                if(i*i!=n&&n/i>=m)
                    res+=euler(i)*(n/i);
            }
        }
        printf("%lld
",res);

응용 3: 1 ~ N 사이 에 x 를 찾 아 gcd (x, N) > = M 을 만족 시 킬 수 있 도록 숫자 N 을 드 립 니 다. 분석: 이 문 제 는 앞의 두 문제 와 대체적으로 같 습 니 다. 최대 공약수 d 를 매 거 할 때 gcd (X, N) = d 의 모든 X 의 합 을 구하 면 됩 니 다.위 에서 알 수 있 듯 이 조건 을 만족 시 키 는 X 개 수 는 euler (N / d) 개가 있 기 때문에 N / d 를 초과 하지 않 고 N / d 와 서로 소 화 된 수의 합 을 구하 고 d 를 곱 하면 최대 공약수 가 d 일 때 대응 하 는 부분 적 인 결과 이다.N / d 를 초과 하지 않 고 N / d 와 호 환 되 는 수의 합 = N / d * euler (N / d) / 2 를 초과 하지 않 습 니 다. N / d = 1 일 때 결 과 는 0 이 아 닌 1 입 니 다.이런 것들 을 이해 하면 이 문 제 를 해결 할 수 있다.1, 2 를 제외 하고 모든 수의 오로라 함 수 는 짝수 이다.만약 k < = n 그리고 (k, n) = 1, 그러면 (n - k, n) = 1;

#include
#include
#include
#include
#include
using namespace std;
#define M 1000000007
typedef long long LL;
LL euler(LL n)
{
    LL ans=n,i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        ans=ans/n*(n-1);
    return ans;
}
LL euler_sum(LL n)
{
    if(n==1)
        return 1;
    return n*(euler(n))/2;
}
int main()
{
    int t;
    LL n,m;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&m);
        LL res=0,i;
        for(i=1;i*i<=n;i++)
        {
            if(n%i==0)
            {
                if(i>=m)
                {
                    res+=euler_sum(n/i)*i;
                    res%=M;
                }
                if(i*i!=n&&n/i>=m)
                {
                    res+=euler_sum(i)*(n/i);
                    res%=M;
                }
            }
        }
        printf("%lld
",res);
    }
    return 0;
}