1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68
| #include<bits/stdc++.h> #include<algorithm> #define LL long long #define PII pair<LL, int> using namespace std; template <class T> inline void read(T &res) { res = 0; bool flag = 0; char c = getchar(); while('0' > c || c > '9') { if(c == '-') flag = 1; c = getchar();} while('0' <= c && c <= '9') res = (res << 3) + (res << 1) + (c ^ 48), c = getchar(); if(flag) res = -res; } template <class T, class ...Arg> inline void read(T &res, Arg &...com){ read(res), read(com...);} template <class T> void out(T res) { if(res > 9) out(res / 10); putchar(res % 10 + '0'); } template <class T> inline void write(T res) { if(res < 0) putchar('-'), res = -res; out(res); } template <> inline void write(char c) { putchar(c); } template <> inline void write(const char *s){ while(*s) putchar(*s ++); } template <class T, class ...ARC> inline void write(T res, ARC ...com) { write(res), write(com...); } const int N = 1e5 + 5, mod = 1e9 + 7; int n; int mu[N], primes[N], cnt, st[N], inv[N]; void init() { mu[1] = 1; for(int i = 2;i < N;i ++) { if(!st[i]) primes[++ cnt] = i, mu[i] = -1; for(int j = 1;j <= cnt && primes[j] * i < N;j ++) { st[primes[j] * i] = 1; if(i % primes[j] == 0) { mu[primes[j] * i] = 0; break; } mu[primes[j]* i] = -mu[i]; } } inv[1] = 1; for(int i = 2;i < N;i ++) inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod; } int ans; int main() { read(n); init(); ans = 1; for(int i = 2;i <= n;i ++) ans = (ans - 1ll * mu[i] % mod * (n / i) % mod * inv[n - n / i] % mod) % mod, ans = (ans + mod) % mod; write(ans); return 0; }
|