开了O2还是T。。看来只能用粉兔的$\sqrt n$算法。还有这题为什么被人称为欧拉反演
by qwq2519 @ 2021-08-31 21:25:40
orz 卡卡常?(雾
by Lzosvje @ 2021-08-31 21:25:51
```
#include<iostream>
#include<cstdio>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
#define bug puts(~~~~~~~);
#define bugout(x) cout<<x<<endl;
using namespace std;
typedef long long lxl;
template<typename T>
inline T max(T &a, T &b) {
return a > b ? a : b;
}
template<typename T>
inline T min(T &a, T &b) {
return a < b ? a : b;
}
inline char gt() {
static char buf[1 << 21], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void read(T &x) {
register char ch = gt();
x = 0;
int w(0);
while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
if(x < 0) x = -x, putchar('-');
char ch[20];
int num(0);
while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
while(num) putchar(ch[num--]);
putchar('\n');
}
lxl n;
inline lxl phi(lxl x){
lxl ans=x;
for(register int i(2);i*i<=n;++i){
if(x%i==0) {
ans=ans/i*(i-1);
while(x%i==0) x/=i;}
}
if(x>1) ans=ans/x*(x-1);
return ans;
}
inline lxl calc(){
lxl ans=0;
for(register int i(1);i*i<=n;++i){
if(n%i==0){
ans+=i*phi(n/i);
if(i*i!=n) ans+=(n/i)*phi(i);
}
}
return ans;
}
int main() {
read(n);
out(calc());
return 0;
}
```
by qwq2519 @ 2021-08-31 21:27:11
@[蒟蒻2519](/user/141335)
可能是 `i * i <= n` 溢出了？
我改成 `i <= n / i` 然后小范围线性筛跑出来过了还跑得飞快
by zimujun @ 2021-08-31 21:39:38
@[zimujunqwq](/user/118196) 是，循环变量i爆int了，加``1ll``过了
by qwq2519 @ 2021-08-31 21:40:12