题目背景
这是一道签到题！
建议做题之前仔细阅读数据范围！
题目描述
我们定义一个函数：qiandao(x)为小于等于x的数中与x不互质的数的个数。
这题作为签到题，给出l和r，要求求。
输入输出格式
输入格式：
一行两个整数，l、r。
输出格式：
一行一个整数表示答案。
输入输出样例
输入样例#1：
233 2333
输出样例#1：
1056499
输入样例#2：
2333333333 2333666666
输出样例#2：
153096296
说明
对于30%的数据，。
对于60%的数据，。
对于100%的数据，，
。
分析：每个数枚举质因数显然超时；
所以，换个角度就是预处理出sqrt（r）的素因子，然后枚举其倍数；
最后欧拉函数即可；
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <bitset> #include <map> #include <queue> #include <stack> #include <vector> #define rep(i,m,n) for(i=m;i<=n;i++) #define mod 1000000007 #define inf 0x3f3f3f3f #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) #define pii pair<int,int> #define sys system("pause") const int maxn=1e6+10; using namespace std; inline ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} inline ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;} inline void umax(ll &p,ll q){if(p<q)p=q;} inline void umin(ll &p,ll q){if(p>q)p=q;} inline ll read() { ll x=0;int f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } int n,m,k,t,cnt[maxn],all; bool vis[maxn]; ll l,r,ret,p[maxn],num[maxn]; void init() { for(int i=2;i<=maxn-10;i++) { if(vis[i])continue; for(int j=2*i;j<=maxn-10;j+=i) { vis[j]=true; } cnt[all++]=i; } } void gao() { for(int i=0;i<all;i++) { ll l1=l%cnt[i]==0?l:(l/cnt[i]+1)*cnt[i],r1=r/cnt[i]*cnt[i]; if(l1>r1)continue; for(ll x=l1;x<=r1;x+=cnt[i]) { p[x-l]-=p[x-l]/cnt[i]; while(num[x-l]%cnt[i]==0) num[x-l]/=cnt[i]; } } for(int i=0;i<=r-l;i++)if(num[i]>1)p[i]-=p[i]/num[i]; } int main() { int i,j; init(); scanf("%lld%lld",&l,&r); for(ll x=l;x<=r;x++)p[x-l]=num[x-l]=x; gao(); for(ll x=l;x<=r;x++)ret=(ret+x-p[x-l])%666623333; printf("%lld\n",ret); return 0; }