Description：

求区间 $[l,r]$ 内小于等于 $x$ 的数中与 $x$ 不互质的数的和。

$1\leqslant l\leqslant r\leqslant 10^{12},r-l\leqslant 10^6$

Solution：

首先就是要求： $$ \sum_{i=l}^ri-\varphi(i) $$ 那么可以区间筛法，由于 $\varphi(x)=x\prod \frac{p_i-1}{p_i}$ ，所以可以用区间筛法处理所有 $\leqslant \sqrt r$ 的 $p_i$ ，最后再处理剩下那个大质数即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

typedef long long ll;

#define MAXN 1000010

bool isprime[MAXN];

int prime[MAXN],tot = 0;

ll phi[MAXN],fac[MAXN];

bool vis[MAXN];

ll l,r;

#define MOD 666623333

int main()

{

	scanf("%lld%lld",&l,&r);

	for(int i = 0;i <= r - l;++i)fac[i] = phi[i] = i + l;

	for(int i = 2;i < MAXN;++i)isprime[i] = true;

	for(int i = 1;i < MAXN;++i)

	{

		if(isprime[i])

		{

			for(int j = i;j < MAXN;j += i)

			{

				isprime[j] = false;

			}

			for(ll j = (l + i - 1) / i * i;j <= r;j += i)

			{

				while(fac[j - l] % i == 0)fac[j - l] /= i;

				phi[j - l] = phi[j - l] / i * (i - 1);

			}

		}

	}

	ll ans = 0;

	for(int i = 0;i <= r - l;++i)

	{

		if(fac[i] != 1)phi[i] = phi[i] / fac[i] * (fac[i] - 1);

		ans = (ans + i + l - phi[i]) % MOD;

	}

	cout << ans << endl;

	return 0;

}