马蜂好评qaq
by Koakuma @ 2019-02-17 14:36:58
int比ll快，我也是，把int改成long long就过了
by LightningUZ @ 2019-02-17 14:53:30
加上`(ll)`或者`1ll*`就不会有问题了
by LightningUZ @ 2019-02-17 14:54:01
@[LightningUZ](/space/show?uid=106252)
意思是
```cpp
ll ans = (x + 1) * x / 2;
```
```cpp
ll ans = (ll)(x + 1) * x / 2;
```
这两个语句运算效率是不一样的吗?
后者会更快一些?
by Hideintime @ 2019-02-17 15:00:34
第一个
```
x+1 O(64)
*x O(64)
/2 O(64)
```
第二个
```
x+1 O(32)
(ll) O(64)
*x O(32)
/2 O(32)
```
而且，每次传一个64位的参数和每次传一个32为的参数肯定是有区别的
(int就是比ll快，快很多2333，就因为它短)
(我是女生请支持$\cdots$)
by LightningUZ @ 2019-02-17 15:06:27
打错了，倒数第3句是
> 而且，每次传一个64位的参数和每次传一个32位(不是"为")的参数肯定是有区别的
by LightningUZ @ 2019-02-17 15:07:14
如果还有问题，参考我的代码
```cpp
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define N 5000000
using namespace std;
template<typename T>inline void read(T &x)
{
x=0;
static int p;p=1;
static char c;c=getchar();
while(!isdigit(c)){if(c=='-')p=-1;c=getchar();}
while(isdigit(c)) {x=(x<<1)+(x<<3)+(c-48);c=getchar();}
x*=p;
}
bool vis[N+1];
int mu[N+1],sum1[N+1];
long long phi[N+1],sum2[N+1];
int cnt,prim[N+1];
int e,e1;
unordered_map<int,long long>w1;
unordered_map<int,int>w;
void get(int maxn)
{
phi[1]=mu[1]=1;
for(int i=2;i<=maxn;i++)
{
if(!vis[i])
{
prim[++cnt]=i;
mu[i]=-1;phi[i]=i-1;
}
for(int j=1;j<=cnt&&prim[j]*i<=maxn;j++)
{
vis[i*prim[j]]=1;
if(i%prim[j]==0)
{
phi[i*prim[j]]=phi[i]*prim[j];
break;
}
else mu[i*prim[j]]=-mu[i],phi[i*prim[j]]=phi[i]*(prim[j]-1);
}
}
for(int i=1;i<=maxn;i++)sum1[i]=sum1[i-1]+mu[i],sum2[i]=sum2[i-1]+phi[i];
}
int djsmu(int x)
{
if(x<=N)return sum1[x];
if(w[x])return w[x];
int ans=1;
for(int l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=(r-l+1)*djsmu(x/l);
}
return w[x]=ans;
}
long long djsphi(int x)
{
if(x<=N)return sum2[x];
if(w1[x])return w1[x];
long long ans=1ll*x*(1ll*x+1)/2;
for(int l=2,r;l<=x;l=r+1)
{
r=x/(x/l);
ans-=1ll*(r-l+1)*djsphi(x/l);
}
return w1[x]=ans;
}
int main()
{
int t;
read(t);
get(5000000);
while(t--)
{
static int n;
read(n);
printf("%lld %d\n",djsphi(n),djsmu(n));
}
return 0;
}
```
~~(有很多的玄学技巧)~~
by LightningUZ @ 2019-02-17 15:08:40
@[LightningUZ](/space/show?uid=106252)
嗯 懂了 谢谢dalao 资瓷资瓷~~（可惜不能对回复点赞233）
by Hideintime @ 2019-02-17 15:10:25
谢谢....($\color{pink}QwQ$)
by LightningUZ @ 2019-02-17 15:20:55
不是吧，后边
``` cpp
r = x / (x / l);
ans -= (r - l + 1) * djsphi(x / l);
```
还是有差距的
by wasa855 @ 2019-02-20 17:44:32