# 链接

[ProjectEuler466]

# 题目大意

$P(3, 4) = 8$

# 题解

$P(64, 10^{16}) = 258381958195474745$

# 代码

#include <map>
#include <cstdio>
#include <cstring>
#include <algorithm>

#define DEBUG(args...) fprintf(stderr, args)

#define FOR(i, l, r) for(int i = (l), i##_end = (r); i <= i##_end; ++i)
#define REP(i, l, r) for(int i = (l), i##_end = (r); i <  i##_end; ++i)
#define DFR(i, l, r) for(int i = (l), i##_end = (r); i >= i##_end; --i)
#define DRP(i, l, r) for(int i = (l), i##_end = (r); i >  i##_end; --i)

typedef long long LL;

template<class T>T Min(const T &a, const T &b) {return a < b ? a : b;}
template<class T>T Max(const T &a, const T &b) {return a > b ? a : b;}
template<class T>bool Chkmin(T &a, const T &b) {return a > b ? a = b, 1 : 0;}
template<class T>bool Chkmax(T &a, const T &b) {return a < b ? a = b, 1 : 0;}

class FastInput {
private:
static const int SIZE = 1 << 15 | 1;
char buf[SIZE], *front, *back;

void Next(char &c) {
if(front == back) back = (front = buf) + fread(buf, 1, SIZE, stdin);
c = front == back ? (char)EOF : *front++;
}

public :
template<class T>void operator () (T &x) {
char c, f = 1;
for(Next(c); c > '9' || c < '0'; Next(c)) if(c == '-') f = -1;
for(x = 0; c >= '0' && c <= '9'; Next(c)) x = x * 10 + c - '0';
x *= f;
}
void operator () (char &c, char l = 'a', char r = 'z') {
for(Next(c); c > r || c < l; Next(c)) ;
}

const int SN = 100000 + 47;
const int SX = 47;

LL Calc(int, LL);
LL Gcd(LL, LL);

int main() {

LL n, m;

n = 64, m = 10000000000000000LL;
//n = 3, m = 10000000000000000LL;

printf("%lld\n", Calc(n, m));

return 0;

}

LL Calc(int x, LL y) {
int min;
LL lcm, t, ans = 0;
std::map<std::pair<int, LL>, LL> f, g;
std::map<std::pair<int, LL>, LL>::iterator it;
g.insert(std::make_pair(std::make_pair(x + 1, 1), -1));
FOR(i, 1, x) {
f = g; DEBUG("%d\n", i);
for(it = f.begin(); it != f.end(); ++it) {
min = Min(i, (it->first).first);
lcm = (it->first).second;
t = i / Gcd(i, lcm);
if(lcm > 1LL * y * min / t) continue;
g[std::make_pair(min, lcm * t)] -= it->second;
}
for(it = g.begin(); it != g.end(); ++it)
if(!it->second)
g.erase(it);
}
for(it = g.begin(); it != g.end(); ++it)
if((it->first).first <= x)
ans += 1LL * y * (it->first).first /
(it->first).second * it->second;
DEBUG("%lu\n", g.size());
return ans;
}

LL Gcd(LL a, LL b) {
return !b ? a : Gcd(b, a % b);
}



STO cai Orz

STO fkl Orz

STO cai Orz