You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
32 lines
919 B
C++
32 lines
919 B
C++
#define _CRT_SECURE_NO_WARNINGS
|
|
#define _SILENCE_CXX17_C_HEADER_DEPRECATION_WARNING
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 5000500, mod = 1e9 + 7;
|
|
int minFac[N];
|
|
long long dp[N];
|
|
int main()
|
|
{
|
|
for (int i = 0; i < N; i++) minFac[i] = i;
|
|
for (int i = 2; i * i < N; i++)
|
|
if (minFac[i] == i)
|
|
for (int j = i * i; j < N; j += i)
|
|
minFac[j] = min(minFac[j], i);
|
|
memset(dp, 0x3f, sizeof(dp));
|
|
dp[1] = 0;
|
|
for (int i = 2; i < N; i++)
|
|
for (int x = i; x != 1; x /= minFac[x])
|
|
dp[i] = min(dp[i], dp[i / minFac[x]] + i * (minFac[x] - 1ll) / 2);
|
|
int t, l, r;
|
|
scanf("%d%d%d", &t, &l, &r);
|
|
long long ans = 0, cnt = 1;
|
|
for (int j = l; j <= r; j++)
|
|
{
|
|
dp[j] %= mod;
|
|
ans = (ans + cnt * dp[j]) % mod;
|
|
cnt = (cnt * t) % mod;
|
|
}
|
|
printf("%lld", ans);
|
|
return 0;
|
|
}
|