搞出了一个不太一样的做法。
本题求$\sum_{i=1}^{N} gcd(i,N)$=$\sum_{d|N} \sum_{i=1}^{N} d[gcd(i,N)=d]$=$\sum_{d|N}\sum_{i=1}^{\lfloor \frac{N}{d} \rfloor}d[gcd(i,j)=1]$=$\sum_{d|N}d\times \phi(\frac{N}{d})$
最后这个式子是$id(n)=n$和欧拉函数的狄利克雷卷积，因为积性函数的狄利克雷卷积也是积性函数，即$F(N)=\sum_{d|N}id(d)\phi(\frac{N}{d})$，对于积性函数，我们只要求出$F(1)、F(p)、F(p^k)$，就能求得任意$F(x)$，明显$F(1)=1$，$F(p)=2*p-1$，根据$\phi(p^k)=p^k-p^{k-1}$，推一推能推出$F(p^k)=p^k+k\times (p-1)\times p^{k-1}$

若$n$=$p_1^{a_1}p_2^{a_2}…p_k^{a_k}$，那我们分解质因数后只需分步求$F(n)=F(p_1^{a_1})F(p_2^{a_2})…F(p_k^{a_k})$

//#define LOCAL
#include <bits/stdc++.h>
using namespace std;
#define DBG printf("%d %s\n",__LINE__,__FUNCTION__)
#define CLOSE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define abs(x) ((x) >= 0 ? (x) : -(x))
#define LF putchar('\n')
#define SP putchar(' ')
#define eb emplace_back
#define mk make_pair
#define sz(x) (int)x.size()
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define eps 1e-6
#define ri register int
#define rl register long long
#define LL long long
#define ULL unsigned long long

template<typename T> 
void read(T &x) {x = 0;char ch = getchar();LL f = 1;while(!isdigit(ch)){if(ch == '-')f *= -1;ch = getchar();}while(isdigit(ch)){x = x * 10 + ch - 48; ch = getchar();}x *= f;}
template<typename T, typename... Args> 
void read(T &first, Args& ... args) {read(first);read(args...);}
template<typename T>
void write(T arg) {T x = arg;if(x < 0) {putchar('-'); x =- x;}if(x > 9) {write(x / 10);}putchar(x % 10 + '0');}
template<typename T, typename ... Ts>
void write(T arg, Ts ... args) {write(arg);if(sizeof...(args) != 0) {putchar(' ');write(args ...);}}

const LL MOD = 1e9 + 7;
const int N = 1e5 + 50;

LL n;
LL prime[N], cnt;
vector<pair<LL, LL> >ve;

bool isprime[N];

void sieve() { // 线性筛
    isprime[1] = 1;
    for(ri i = 2; i < N; ++i) {
        if(!isprime[i]) {
            prime[cnt++] = i;
        }
        for(ri j = 0; j < cnt && i * prime[j] < N; ++j) {
            isprime[i*prime[j]] = 1;
            if(i % prime[j] == 0) {
                break;
            }
        }
    }
}

void fj(LL k) {
    LL kc = k;
    for(ri i = 0; i < cnt && prime[i] * prime[i] <= k; ++i) {
        if(kc % prime[i] == 0) {
            LL tmp = 0;
            while(kc % prime[i] == 0) {
                kc /= prime[i];
                ++tmp;
            }
            ve.eb(mk(prime[i], tmp));
        }
        if(kc == 1) {
            break;
        }
    }
    if(kc != 1) {
        ve.eb(mk(kc, 1));
    }
}

LL qpow(LL a, LL p) {
    LL sum = 1;
    while(p) {
        if(p & 1) {
            sum = sum * a;
        }
        a = a * a;
        p >>= 1;
    }
    return sum;
}

int main() {
#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    sieve();
    read(n);
    fj(n);
    LL ans = 1;
    for(ri i = 0; i < sz(ve); ++i) {
        ans *= qpow(ve[i].first, ve[i].second) + ve[i].second * (ve[i].first - 1) * qpow(ve[i].first, ve[i].second - 1);
    }
    write(ans), LF;
    return 0;
}