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 ^ 2 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

#include

#include 
using namespace std;
const int mod =1e9+7;
set S;
int n;
int main() {
    cin>>n;
    int res=1ll*n*(n*2-1)%mod;
    for(int i=2;i*i<=n;i++){
        if(S.find(i)!=S.end()) continue;//s    
        long long tmp=1;
        int cnt=0;
        while(tmp<=n){
            S.insert(tmp);
            tmp=tmp*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;
            }
        } 
    }
	cout<