天津网站优化公司,手表网站查询,wordpress营销,wordpress 前端用户P1829 [国家集训队]Crash的数字表格 / JZPTAB
题意#xff1a;
求∑i1n∑j1mlcm(i,j)\sum_{i1}^{n}\sum_{j1}^{m}lcm(i,j)∑i1n∑j1mlcm(i,j) 1nm1e7 结果mod20101009
题解#xff1a;
跟这个题P3911 最小公倍数之和很相近#xff0c;但是本题数据范围大…P1829 [国家集训队]Crash的数字表格 / JZPTAB
题意
求∑i1n∑j1mlcm(i,j)\sum_{i1}^{n}\sum_{j1}^{m}lcm(i,j)∑i1n∑j1mlcm(i,j) 1nm1e7 结果mod20101009
题解
跟这个题P3911 最小公倍数之和很相近但是本题数据范围大 tmp是整数分块过程中d在[l,r]这段区间的累加
ll tmp ((1ll * r * (r 1) / 2) - (1ll * (l - 1) * l / 2)) % mod;代码
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 2e7 9;
const int mod 20101009;
int prime[maxn], mu[maxn];
int vis[maxn];
ll sum[maxn];
int cnt 0;
void get_mu(int N)
{mu[1] 1;vis[1] vis[0] 1;for (int i 2; i N; i) {if (!vis[i]) {prime[cnt] i;mu[i] -1;}for (int j 1; j cnt i * prime[j] N; j) {vis[i * prime[j]] 1;if (i % prime[j] 0)break;mu[i * prime[j]] -mu[i];}}for (int i 1; i N; i) {sum[i] (sum[i - 1] 1ll * i * i % mod * mu[i] % mod) % mod;}
}
ll f(int x, int y)
{ll ans (1ll * x * (x 1) / 2) % mod * (1ll * y * (y 1) / 2 % mod) % mod;return ans % mod;
}
ll Sum(int x, int y)
{ll ans 0;for (int l 1, r; l min(x, y); l r 1) {r min(x / (x / l), y / (y / l));ans (ans 1ll * (sum[r] - sum[l - 1] mod) % mod * f(x / l, y / l) % mod) % mod;}//cout ans ans endl;return ans % mod;
}
ll poww(ll a, ll b)
{ll ans 1;while (b) {if (b 1)ans ans * a % mod;a a * a % mod;b 1;}return ans % mod;
}
int main()
{get_mu(10000002);//rd_test();int n, m;read(n, m);int minn min(n, m);ll ans 0;for (int l 1, r; l minn; l r 1) {r min(n / (n / l), m / (m / l));ll tmp ((1ll * r * (r 1) / 2) - (1ll * (l - 1) * l / 2)) % mod;ans (ans tmp * Sum(n / l, m / l) % mod) % mod;//cout ans % mod endl;}cout ans % mod;//Time_test();
}
