경 동 2018 가을 붓 시험 문제 의 멱

동 동 은 멱 연산 에 관심 이 많 습 니 다. 공부 하 는 과정 에서 중동 동 에서 재 미 있 는 성질 을 발 견 했 습 니 다. 9 ^ 3 = 27 ^ 2, 2 ^ 10 = 32 ^ 2 동 동 동 은 이 성질 에 대해 호기심 이 많 습 니 다. 동 동 동 은 지금 정수 n 을 제시 하고 있 습 니 다. 그 가 a ^ b = c ^ d (1 ≤ a, b, c, d ≤ n) 의 식 이 몇 개 인지 구 할 수 있 도록 도와 주 십시오.예 를 들 어 n = 2: 1 ^ 1 = 1 ^ 1 1 ^ 1 = 1 ^ 2 = 1 ^ 2 = 1 ^ 2 ^ 1 = 2 ^ 1 2 ^ 2 = 2 ^ 2 = 2 ^ 2 모두 6 개의 요 구 를 만족 시 키 는 식 입력 설명 이 있 습 니 다. 입력 은 정수 n (1 ≤ n ≤ 10 ^ 6) 을 포함 합 니 다.
출력 설명: 요 구 를 만족 시 키 는 식 개 수 를 나타 내 는 정 수 를 출력 합 니 다.답 이 많 을 수 있 기 때문에 출력 은 1000000007 모델 을 구 하 는 결과 예제 1 입 출력 2 입 출력 6 입 니 다.
지식 포인트: set 집합 중복 데이터 없 음, C + STL 함수.(i ^ x) ^ c = (i ^ y) ^ d 는 사실 x * c = y * d 를 의미 하고 (x / y) = (d / c), x, y 를 매 거 할 수 있 으 며, 예비 처 리 를 통 해 사실은 몇 쌍 (c, d) 을 구 하 는 것 이다.

#include 
using namespace std;
const int mod=1e9+7;
set<int> S;
int n;
int main()
{
    scanf("%d",&n);
    int res=1LL*n*(n*2-1)%mod;
    for(int i=2; i*i<=n; i++)
    {
        if(S.find(i)!=S.end())
            continue;
        long long temp=i;
        int cnt=0;
        while(temp<=n)
        {
            S.insert(temp);
            temp=temp*i;
            cnt++;
        }
        for(int i=1; i<=cnt; i++)
        {
            for(int j=i+1; j<=cnt; j++)
            {
                res=(res+n/(j/__gcd(i,j))*2LL)%mod;
            }
        }
    }
    printf("%d
",res);
    return 0;
}