# 题解 P4317 花神的数论题()-其他

## 题解 P4317 花神的数论题()

``````//SIXIANG
#include <iostream>
#include <cstring>
#define MAXN 100000
#define int long long
#define QWQ cout << "QWQ" << endl;
using namespace std;
const int Mod = 10000000 + 7;
int qpow(int n, int m) {
int res = 1;
while(m) {
if(m & 1) res = res * n % Mod;
n = n * n % Mod, m >>= 1;
}
return res;
}
int f[200][50][2][2], tot, arr[MAXN + 10];
int pika(int i, int s, int limit, int lead, int num, int o) {
if(!i) return (s == o);
int lim = ((limit) ? (arr[i]) : 1), rest = 0;
for(int p = 0; p <= lim; p++)
rest += pika(i - 1, s + (p == 1), limit && (p == arr[i]), lead && (!p), (num << 1) + p, o);
return rest;
}
int solve(int x) {
do {
arr[++tot] = x % 2;
x >>= 1;
} while(x);
int mul = 1;

for(int p = 1; p <= 49; p++) {
memset(f, -1, sizeof(f));
int res = pika(tot, 0, 1, 1, 0, p);
mul = mul * qpow(p, res) % Mod;
}
return mul;
}
signed main() {
int n; cin >> n;
cout << solve(n) << endl;
}
``````
————————

``````//SIXIANG
#include <iostream>
#include <cstring>
#define MAXN 100000
#define int long long
#define QWQ cout << "QWQ" << endl;
using namespace std;
const int Mod = 10000000 + 7;
int qpow(int n, int m) {
int res = 1;
while(m) {
if(m & 1) res = res * n % Mod;
n = n * n % Mod, m >>= 1;
}
return res;
}
int f[200][50][2][2], tot, arr[MAXN + 10];
int pika(int i, int s, int limit, int lead, int num, int o) {
if(!i) return (s == o);
int lim = ((limit) ? (arr[i]) : 1), rest = 0;
for(int p = 0; p <= lim; p++)
rest += pika(i - 1, s + (p == 1), limit && (p == arr[i]), lead && (!p), (num << 1) + p, o);
return rest;
}
int solve(int x) {
do {
arr[++tot] = x % 2;
x >>= 1;
} while(x);
int mul = 1;

for(int p = 1; p <= 49; p++) {
memset(f, -1, sizeof(f));
int res = pika(tot, 0, 1, 1, 0, p);
mul = mul * qpow(p, res) % Mod;
}
return mul;
}
signed main() {
int n; cin >> n;
cout << solve(n) << endl;
}
``````