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
|
#define REP(i, a, b) for (int i = a; i <= b; ++i) #define PER(i, a, b) for (int i = a; i >= b; --i) #define RVC(i, S) for (int i = 0; i < S.size(); ++i) #define mp make_pair #define pb push_back #define debug(...) fprintf(stderr, __VA_ARGS__) #define fi first #define se second using namespace std;
typedef long long LL; typedef pair<int, int> pii; typedef vector<int> VI;
const int N = 500005, mo = 1000000007; int n, m, nop[N], pr[N], mu[N], p[N], sp[N];
void (){ mu[1] = 1; REP(i, 2, n){ if (!nop[i]) pr[++pr[0]] = i, mu[i] = -1; for (int j = 1; j <= pr[0] && i * pr[j] <= n; ++j){ nop[i * pr[j]] = 1; if (i % pr[j] == 0){ mu[i * pr[j]] = 0; break; } mu[i * pr[j]] = -mu[i]; } } }
inline int add(int x, int y){ x += y; if (x < 0) x += mo; if (x >= mo) x -= mo; return x; }
LL pwr(LL a, LL b){ LL res = 1; for (; b; b >>= 1, (a *= a) %= mo) if (b & 1) (res *= a) %= mo; return res; }
int main(){ scanf("%d%d", &n, &m); if (n < m) swap(n, m); sieve(); REP(i, 1, n) p[i] = 1; int ans = 0; REP(g, 1, m){ for (int d = 1; d * g <= n; ++d){ p[d] = 1ll * p[d] * d % mo; sp[d] = add(sp[d - 1], p[d]); } LL sum = 0; for (int d = 1; d * g <= m; ++d){ LL tmp = 1ll * sp[n / (g * d)] * sp[m / (g * d)] % mo; tmp = tmp * p[d] % mo * p[d] % mo; sum = add(sum, mu[d] * tmp); } ans = add(ans, sum * pwr(g, g) % mo); } printf("%dn", ans); return 0; }
|
近期评论