long long
by ws_yzy @ 2015-08-17 18:01:35
@[url=/space/show?uid=4039]ws\_yzy[/url] 已经设置longlong了……
[codec]
```cpp
#include <iostream>
using namespace std;
int main()
{
int n;
long long ans = 0;
cin >> n;
long long f[n];
for(int d=n;d>=1;d--)
{
f[d]= 1ll*(1ll*(n/d))*1ll*(1ll*(n/d));
for(int i= d+d; i <= n; i += d) f[d]-=f[i];
ans += f[d]*d;
}
printf("%I64d\n", ans);
return 0;
}
[/codec]
```
by cuvid @ 2015-08-17 18:38:14
@[url=/space/show?uid=4039]ws\_yzy[/url] 已经设置longlong了……
[codec]
```cpp
#include <iostream>
using namespace std;
int main()
{
int n;
long long ans = 0;
cin >> n;
long long f[n];
for(int d=n;d>=1;d--)
{
f[d]= 1ll*(1ll*(n/d))*1ll*(1ll*(n/d));
for(int i= d+d; i <= n; i += d) f[d]-=f[i];
ans += f[d]*d;
}
printf("%I64d\n", ans);
return 0;
}
[/codec]
```
by cuvid @ 2015-08-17 18:43:00
标程长这样←\_←，复杂度竟然是NlgN的，虽然很好理解，但是明显可以O(N)啊。。
by yjqqqaq @ 2015-08-17 20:09:53
@[url=/space/show?uid=7428]yjqqqaq[/url] 请教大神……怎么写O（n）的……
by cuvid @ 2015-08-18 19:30:57
@[url=/space/show?uid=4860]cuvid[/url] 用一下一个公式就可以了，sigma(phi(d) (当d|n)) = n，然后可以把求的式子化简。用代码可以这样表示
本来要求的:for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) gcd(i,j);
变成：for (int I=1;i<=n;i++) for (int j=1;j<=n;j++) for (int d=1;d<=n;d++) if (gcd(i,j) %d == 0) ans += phi(d);
发现d|gcd(i,j) 等价于d|i 并且d|j，
代码变成for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int d=1;d<=n;d++) if (d | i && d | j) ans += phi(d)
我们单独考虑每个d的贡献，就变成了
for (int d=1;d<=n;d++) ans += phi(d) \*(n / d) \* (n / d)
O(N)处理出所有phi可以用类似于素数筛的方法做到，所以总共就是O(n)的
by yjqqqaq @ 2015-08-19 15:15:09
@[url=/space/show?uid=4860]cuvid[/url] 我好像看到了你的(int n ) 感觉全都longlong 就能过吧
by ws_yzy @ 2015-08-19 20:11:27
orz O(n)大爷
by laphets @ 2015-08-29 13:41:44
@[cuvid](/space/show?uid=4860) 你printf从哪里来的？？？？？iostream里面有吗？？？？？编译都过不了好吗？？？？？
by never_see @ 2017-02-22 21:02:31
# @[never\_see](/space/show?uid=20116) **printf**在**stdio.h**和**cstdio**里。
by clarkwang @ 2017-11-02 20:44:49