今天没啥魔怔事好像，但是为啥莫反式子这么长我都怀疑我怎么打出来的
推歌：世末歌者/乐正绫 by COPY
简要题意：
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^kf(\gcd(i,j))\gcd(i,j)
\]
如果 \(k\) 有平方因子 \(f(k)=0\)，否则 \(f(k)=1\)。
容易发现\(f(k)=\mu^2(k)\)
\[\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k\mu^2(\gcd(i,j))\gcd(i,j)
\]
\[\sum_{d=1}^{n}d\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k\mu^2(d)[\gcd(i,j)=d]
\]
\[\sum_{d=1}^{n}d\times \mu^2(d)\sum\limits_{i=1}^n\sum\limits_{j=1}^n(i+j)^k[\gcd(i,j)=d]
\]
\[\sum_{d=1}^{n}d^{k+1}\times \mu^2(d)\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}(i+j)^k[\gcd(i,j)=1]
\]
\[\sum_{d=1}^{n}d^{k+1}\times \mu^2(d)\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}(i+j)^k\sum_{q|\gcd(i,j)}\mu(q)
\]
\[\sum_{d=1}^{n}d^{k+1} \mu^2(d)\sum_{q|\gcd(i,j)}\mu(q)q^k\sum\limits_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac nd\rfloor}(i+j)^k
\]
那一堆\(\mu\)直接线性筛就行然后预处理\(i^k\)的值似乎也可以
这个简单题，和YY的GCD没啥太大区别感觉
根据简单的容斥原理
\[\sum_{i=1}^{b}\sum_{j=1}^{d}[\gcd(i,j)=k]-
\sum_{i=1}^{a-1}\sum_{j=1}^{d}[\gcd(i,j)=k]-
\sum_{i=1}^{b}\sum_{j=1}^{c-1}[\gcd(i,j)=k]+
\sum_{i=1}^{a}\sum_{j=1}^{c}[\gcd(i,j)=k]
\]
\[\sum_{i=1}^{\lfloor \frac bk \rfloor }\sum_{j=1}^{\lfloor \frac dk \rfloor }[\gcd(i,j)=1]-
\sum_{i=1}^{\lfloor \frac {a-1}k \rfloor }\sum_{j=1}^{\lfloor \frac dk \rfloor }[\gcd(i,j)=1]-
\sum_{i=1}^{\lfloor \frac bk \rfloor }\sum_{j=1}^{\lfloor \frac {c-1}k \rfloor }[\gcd(i,j)=1]+
\sum_{i=1}^{\lfloor \frac ak \rfloor }\sum_{j=1}^{\lfloor \frac ck \rfloor }[\gcd(i,j)=1]
\]
\[\sum_{i=1}^{\lfloor \frac bk \rfloor }\sum_{j=1}^{\lfloor \frac dk \rfloor }\sum_{d|\gcd(i,j)}\mu(d)-
\sum_{i=1}^{\lfloor \frac {a-1}k \rfloor }\sum_{j=1}^{\lfloor \frac dk \rfloor }\sum_{d|\gcd(i,j)}\mu(d)-
\sum_{i=1}^{\lfloor \frac bk \rfloor }\sum_{j=1}^{\lfloor \frac {c-1}k \rfloor }\sum_{d|\gcd(i,j)}\mu(d)+
\sum_{i=1}^{\lfloor \frac ak \rfloor }\sum_{j=1}^{\lfloor \frac ck \rfloor }\sum_{d|\gcd(i,j)}\mu(d)
\]
\[\sum_{d=1}^{\min(b,d)}\mu(d)\lfloor \frac bk \rfloor \lfloor \frac dk \rfloor -
\sum_{d=1}^{\min(a-1,d)}\mu(d)\lfloor \frac {a-1}k \rfloor\lfloor \frac dk \rfloor -
\sum_{d=1}^{\min(b,c-1)}\mu(d)\lfloor \frac bk \rfloor \lfloor \frac {c-1}k \rfloor +
\sum_{d=1}^{\min(a,c)}\mu(d)\lfloor \frac ak \rfloor \lfloor \frac ck \rfloor
\]
然后就没了，直接筛筛筛预处理预处理预处理就行
我发现我好多比较基础的数论概念都不知道，顺便了解一下
先学点比较基础的
复数
引入 \(\text i\) 定义 \(\text i^2=-1\)
定义形如 \(a+b\text{i}\) 的代数式为 复数，其中 \(\text i\) 被称作虚数单位，全体复数的集合是复数集 \(\mathbf{C}\)
复数用 \(z\) 表示，也就是 \(z=a+b\text i\)，这种形式叫复数的代数形式,其中\(a\)叫做\(z\)的实部( 也就是\(\text{Re}(z)\) )，\(b\)叫做\(z\)的虚部( 也就是\(\text{Im}\)(z) )
对于一个复数 \(z\) ，当且仅当 \(b=0\) 时，它是实数，当 \(b\ne 0\) 时，它是虚数，当 \(a=0\) 且 \(b\ne 0\) 时，它是纯虚数
-
共轭
对于实数\(z=a+b\text i\)，\(z\)的共轭复数\(\bar z=a-b\text i\)，可以发现\(\bar z\)和\(z\)对于实数轴对称
对于复数 \(z,w\) ，复数共轭有如下性质
\[z\cdot\bar{z}=|z|^2 \]\[\overline{\overline{z}}=z \]\[\operatorname{Re}(z)=\dfrac{z+\bar{z}}{2} \]\[\operatorname{Im}(z)=\dfrac{z-\bar{z}}{2} \]\[\overline{z\pm w}=\bar{z}\pm\bar{w} \]\[\overline{zw}=\bar{z}\bar{w} \]\[\overline{z/w}=\bar{z}/\bar{w} \]几条性质看起来都是显而易见的
-
欧拉公式
对任意实数 \(x\) ，有 $\mathrm{e}^{\mathrm{i}x}=\cos x+\mathrm{i}\sin x $
恼了，我为啥要学这个？
哦好像是因为莫反不是说有前置的那个卷积吗然后卷积好像又有这个前置条件
-
\(\text{Dirichlet}\) 卷积
\(\mathcal{P}\) 表示所有质数
对于数论函数 \(f(x)\) 和 \(g(x)\) ，则她们的 \(\text{Dirichlet}\)卷积 得到的结果 \(h(x)\) 定义为
\[h(x)=\sum_{d\mid x}{f(d)g\left(\dfrac xd \right)}=\sum_{ab=x}{f(a)g(b)} \]这是啥?
直接简记为
\[h=f*g \]交换律： \(f*g=g*f\) 。
结合律： \((f*g)*h=f*(g*h)\) 。
分配律： \((f+g)*h=f*h+g*h\) 。
等式的性质： \(f=g\) 的充要条件是 \(f*h=g*h\) ，其中数论函数 \(h(x)\) 要满足 \(h(1)\ne 0\) 。
剩下的明天学咕咕咕
去别处抄的$\text{Fastio}$
#include<bits/stdc++.h>
namespace Fast_I {char *_Buf, *_Start_ptr, *_End_ptr;std::streambuf* inbuf;unsigned int Size;bool _Ok;struct Fast_Istream {operator bool(){return _Ok; }Fast_Istream(std::streambuf*, unsigned int);Fast_Istream(unsigned int);Fast_Istream(const char*, unsigned int);Fast_Istream& operator>>(char&);Fast_Istream& operator>>(char*);Fast_Istream& operator>>(bool&);Fast_Istream& operator>>(short&);Fast_Istream& operator>>(int&);Fast_Istream& operator>>(long&);Fast_Istream& operator>>(long long&);Fast_Istream& operator>>(unsigned short&);Fast_Istream& operator>>(unsigned int&);Fast_Istream& operator>>(unsigned long&);Fast_Istream& operator>>(unsigned long long&);Fast_Istream& operator>>(float&);Fast_Istream& operator>>(double&);Fast_Istream& operator>>(long double&);Fast_Istream& operator>>(std::string&);template <typename Typex>void operator()(Typex& _Val) { *this >> _Val; }template <typename Typex, typename... More>void operator()(Typex&, More&...);std::streambuf* rdbuf() { return inbuf; }void rdbuf(std::streambuf* _inbuf) { inbuf = _inbuf; }void rdbuf(const char*);void pop();char peek();};}
namespace Fast_O {std::string buf;std::streambuf* outbuf;struct Fast_Ostream {Fast_Ostream(std::streambuf*, unsigned int);Fast_Ostream(std::streambuf* out) { outbuf = out; }Fast_Ostream(const char*, unsigned int);Fast_Ostream(unsigned int);void flush();~Fast_Ostream();void endl() { buf.push_back('\n'); }template <typename Typex>void endl(const Typex& _Val);template <typename Typex, typename... More>void endl(const Typex&, const More&...);template <typename Typex>void operator()(const Typex& _Val);template <typename Typex, typename... More>void operator()(const Typex&, const More&...);Fast_Ostream& operator<<(char);Fast_Ostream& operator<<(const char*);Fast_Ostream& operator<<(const std::string&);Fast_Ostream& operator<<(bool);Fast_Ostream& operator<<(short);Fast_Ostream& operator<<(int);Fast_Ostream& operator<<(long);Fast_Ostream& operator<<(long long);Fast_Ostream& operator<<(unsigned short);Fast_Ostream& operator<<(unsigned int);Fast_Ostream& operator<<(unsigned long);Fast_Ostream& operator<<(unsigned long long);std::streambuf* rdbuf() { return outbuf; }void rdbuf(std::streambuf* _outbuf) { outbuf = _outbuf; }void rdbuf(const char*);};}
namespace Fast_IO {Fast_I::Fast_Istream fin(std::cin.rdbuf(), 1048576);Fast_O::Fast_Ostream fout(std::cout.rdbuf()); }
#define cin Fast_IO::fin
#define cout Fast_IO::fout
namespace Fast_I {Fast_Istream::Fast_Istream(std::streambuf* in, unsigned int Sz) {_Ok = 1;Fast_I::Size = Sz;inbuf = in;_Start_ptr = _End_ptr = _Buf = new char[Sz];}Fast_Istream::Fast_Istream(const char* in, unsigned int Sz) {_Ok = 1;Fast_I::Size = Sz;rdbuf(in);_Start_ptr = _End_ptr = _Buf = new char[Sz];}Fast_Istream::Fast_Istream(unsigned int Sz) {_Ok = 1;Fast_I::Size = Sz;_Start_ptr = _End_ptr = _Buf = new char[Sz];}void Fast_Istream::rdbuf(const char* File) {static std::ifstream __In__(File);rdbuf(__In__.rdbuf());}void Get_Char(char& _Val) {if (_Start_ptr == _End_ptr) {_Start_ptr = _Buf;_End_ptr = _Buf + inbuf->sgetn(_Buf, Size);}if (_Start_ptr == _End_ptr) {_Val = -1;_Ok = 0;} else {_Val = *_Start_ptr++;}}Fast_Istream& Fast_Istream::operator>>(char& _Val) {if(_Ok){Get_Char(_Val);while (_Val == 32 || _Val == 10 || _Val == 13 || _Val == 8 || _Val == 9 || _Val == 7 || _Val == 12 || _Val == 11) {Get_Char(_Val);}}return *this;}Fast_Istream& Fast_Istream::operator>>(char* _Val) {if (_Ok) {Get_Char(*_Val);while (*_Val == 32 || *_Val == 10 || *_Val == 13 || *_Val == 8 ||*_Val == 9 || *_Val == 7 || *_Val == 12 || *_Val == 11) {Get_Char(*_Val);}while (*_Val != 32 && *_Val != 10 && *_Val && *_Val != -1 && *_Val != 9 &&*_Val != 11 && *_Val != 12) {Get_Char(*++_Val);}*_Val = 0;--_Start_ptr;}return *this;}Fast_Istream& Fast_Istream::operator>>(std::string& _Val) {if (_Ok) {char c;Get_Char(c);while (c == 32 || c == 10 || c == 13 || c == 8 || c == 9 || c == 7 ||c == 12 || c == 11) {Get_Char(c);}for (_Val.clear();c != 32 && c != 10 && c && c != -1 && c != 9 && c != 11 && c != 12;Get_Char(c)) {_Val.push_back(c);}--_Start_ptr;}return *this;}template <typename Typex>void Get_Int(Typex& _Val) {if (_Ok) {char ch;bool _F = 0;for (Get_Char(ch); (ch < 48 || ch > 57) && ch != -1; Get_Char(ch)) {_F = ch == 45;}for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val = _Val * 10 + (ch ^ 48);}if (_F) {_Val = ~_Val + 1;}--_Start_ptr;}}template <typename Typex>void Get_Unsigned(Typex& _Val) {if (_Ok) {char ch;Get_Char(ch);while ((ch < 48 || ch > 57) && ch != -1) {Get_Char(ch);}for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val = _Val * 10 + (ch ^ 48);}--_Start_ptr;}}template <typename Typex>void Get_Double(Typex& _Val) {if(_Ok){char ch;bool _F = 0;for (Get_Char(ch); (ch < 48 || ch > 57) && ch != -1; Get_Char(ch)) {_F = ch == 45;}for (_Val = 0; ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val = _Val * 10 + (ch ^ 48);}if (ch == 46) {unsigned long long _Pow = 1;for (Get_Char(ch); ch > 47 && ch < 58 && ch != -1; Get_Char(ch)) {_Val += Typex((ch ^ 48) * 1.0 / (_Pow *= 10));}}if (_F) {_Val = -_Val;}--_Start_ptr;}}Fast_Istream& Fast_Istream::operator>>(bool& _Val) {if(_Ok){char ch;Get_Char(ch);while (ch == 32 || ch == 10 || ch == 13 || ch == 8 || ch == 9 || ch == 7 ||ch == 12 || ch == 11) {Get_Char(ch);}while (ch != 32 && ch != 10 && ch && ch != -1 && ch != 9 && ch != 11 &&ch != 12) {_Val |= ch != 48;Get_Char(ch);}--_Start_ptr;}return *this;}Fast_Istream& Fast_Istream::operator>>(short& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(int& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(long& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(long long& _Val) {Get_Int(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned short& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned int& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned long& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(unsigned long long& _Val) {Get_Unsigned(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(float& _Val) {Get_Double(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(double& _Val) {Get_Double(_Val);return *this;}Fast_Istream& Fast_Istream::operator>>(long double& _Val) {Get_Double(_Val);return *this;}template <typename Typex, typename... More>void Fast_Istream::operator()(Typex& _Val, More&... _More) {*this >> _Val;operator()(_More...);}void Fast_Istream::pop() {char ch;Get_Char(ch);}char Fast_Istream::peek() {if (_Start_ptr == _End_ptr) {_Start_ptr = _Buf;_End_ptr = _Buf + inbuf->sgetn(_Buf, Size);}if (_Start_ptr == _End_ptr) {_Ok = 0;return -1;} else {return *_Start_ptr;}}}
namespace Fast_O {Fast_Ostream::Fast_Ostream(std::streambuf* out, unsigned int Size) {buf.reserve(Size);outbuf = out;}Fast_Ostream::Fast_Ostream(const char* File, unsigned int Size) {buf.reserve(Size);rdbuf(File);}void Fast_Ostream::rdbuf(const char* File) {static std::ofstream __Out__(File);rdbuf(__Out__.rdbuf());}Fast_Ostream::Fast_Ostream(unsigned int Size) {buf.reserve(Size);}void Fast_Ostream::flush() {outbuf->sputn(buf.data(), buf.size());buf.clear();}Fast_Ostream::~Fast_Ostream() {flush();}Fast_Ostream& Fast_Ostream::operator<<(char _Val) {buf.push_back(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(const char* _Val) {while (*_Val) {buf.push_back(*_Val++);}return *this;}Fast_Ostream& Fast_Ostream::operator<<(const std::string& _Val) {for (auto&& i : _Val) {buf.push_back(i);}return *this;}template <typename Typex>void Put_Unsigned(Typex _Val) {char* _Stack = (char*)malloc(sizeof(Typex) * 3);unsigned S_top = 0;while (_Val) {_Stack[++S_top] = (_Val % 10) ^ 48;_Val /= 10;}if (!S_top) {buf.push_back('0');}while (S_top) {buf.push_back(_Stack[S_top--]);}free(_Stack);}void Put_Int(long long _Val) {if (_Val < 0) {buf.push_back('-');Put_Unsigned(~_Val + 1);} else {Put_Unsigned(_Val);}}Fast_Ostream& Fast_Ostream::operator<<(bool _Val) {buf.push_back(_Val ? '1' : '0');return *this;}Fast_Ostream& Fast_Ostream::operator<<(short _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(int _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(long _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(long long _Val) {Put_Int(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned short _Val) {Put_Unsigned(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned int _Val) {Put_Unsigned(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned long _Val) {Put_Unsigned(_Val);return *this;}Fast_Ostream& Fast_Ostream::operator<<(unsigned long long _Val) {Put_Unsigned(_Val);return *this;}template <typename Typex>void Fast_Ostream::endl(const Typex& _Val) {*this << _Val << '\n';}template <typename Typex, typename... More>void Fast_Ostream::endl(const Typex& _Val, const More&... _More) {*this << _Val;endl(_More...);}template <typename Typex>void Fast_Ostream::operator()(const Typex& _Val) {*this << _Val;}template <typename Typex, typename... More>void Fast_Ostream::operator()(const Typex& _Val, const More&... _More) {*this << _Val;operator()(_More...);}}
signed main() {
int a, b;
cin(a, b);// cin >> a >> b;
cout(a + b, '\n'); // cout << a + b << '\n'; // cout.endl(a + b);
return 0;
}
