欧拉反演(网上起的名字。。的)的模板题
公式推导见https://www.cnblogs.com/QQ2519/p/15212552.html
my code:
#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('
');
}
lxl n;
namespace solve1 {
inline lxl phi(lxl x) {
lxl ans = x;
for(register int i(2); 1ll * i * i <= n; ++i) {
if(x % i == 0) {
ans = (1ll * ans / i * (i - 1));
while(x % i == 0) x /= i;
}
}
if(x > 1) ans = (1ll * ans / x * (x - 1) );
return ans;
}
inline lxl calc() {
lxl ans = 0;
for(register int i(1); 1ll * i * i <= n; ++i) {
if(n % i == 0) {
ans += i * phi(n / i);
if(i * i != n) ans += (n / i) * phi(i);
}
}
return ans;
}
}
namespace solve2 {
long long f() {
long long ans = n;
long long i;
for(i = 2; i * i <= n; ++i) if(n % i == 0) {
int b = 0;
while(n % i == 0) ++b, n /= i;
ans =ans/ i*(b*i-b+i);
}
if(n > 1) ans=ans/n*(n+n-1) ;
return ans;
}
}
int main() {
read(n);
out(solve2::f());
return 0;
}