멱 (경 동 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

사고방식: 폭력 은 틀림없이 시간 을 초과 할 것 이다. 어떤 기교가 있 을 까?a ^ b = c ^ d 는 이러한 형식 (i ^ x) ^ b = (i ^ y) ^ d, 폭력 i 를 동시에 옮 겨 다 닐 수 있 습 니 다.
/**
a^c=b^d----->(i^x)^c = (i^y)^d
  i, i^x<=n、j^y<=n,  x y   
  x y,  x y           i   ,
x y           m     (c d)       n  , n/m
*/
#include
#include
using namespace std;
int MOD = 1000000000 + 7;
int gcd(int a,int b){
    return (a % b == 0) ? b : gcd(b,a%b);
}
int main() {
    int n;
    cin>>n;
    //int   ,          
    long long ans =(long long) 1*n*(n*2-1) % MOD;
    set s;
    //  i
    for (int i = 2; i*i <= n; i++){
        if ( s.find(i)!=s.end()) continue;
        int tmp = i;
        int cnt = 0;
        //       ,   x y   
        while(tmp <= n) {
            s.insert(tmp);
            tmp = tmp * i;
            cnt++;
        }
        //      ,    ,      n
        for(int k = 1; k <= cnt; k++) {
            for(int j = k + 1; j <= cnt; j++) {
                ans = (ans + n / (j / gcd(k, j) ) * (long)2 ) % MOD;
            }
        }
    }
    cout<

좋은 웹페이지 즐겨찾기