题目链接：
https://projecteuler.net/problem=516
题目：
\(5\)-smooth numbers are numbers whose largest prime factor doesn't exceed \(5\).
\(5\)-smooth numbers are also called Hamming numbers.
Let S(L) be the sum of the numbers \(n\) not exceeding \(L\) such that Euler's totient function \(φ(n)\) is a Hamming number.
S(\(100\))=\(3728\).
Find S(\(10^{12}\)). Give your answer modulo \(2^{32}\).
题解：
因为：
如果 \(n\) 是质数，则\(φ(n)=n-1\)
如果 \(n\) 是质数，则\(φ(n^k) = n^k *(n-1)\)
如果 \(x\) 和 \(y\) 互质，则\(φ(xy) = φ(x) * φ(y)\)
而且，\(5\)-smooth number 可以表示成 \(2^a 3^b 5^c\)
那么我们可以容易得到：
题目要求的就是：\(n = 2^a 3^b 5^c \cdot p_1 \cdot p_2 \cdot \dotso \cdot p_k\)。
其中，\(p_i = 2^{a_i} 3^{b_i} 5^{c_i} + 1\)。
直接预处理所有 \(10^{12}\) 内的 \(p_i\)，然后暴搜所有可能的乘积。
把这些可能的结果相加起来就是答案。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e8;
const int mod = 1e9;
const ll limit = 1e12;
int isprime(ll x)
{
if(x<=1)return 0;
for(ll i = 2;i * i <= x; i++) {
if(x % i == 0) {
return 0;
}
}
return 1;
}
ll ans = 0;
std::vector<ll> v;
// n = 2^a * 3^b * 5^c * p_1 *p_2*...*p_k
// where p_i = 2^a_i * 3^b_i * 5^ c_i + 1
//generate all the possible products and sum them
void dfs(ll id,ll now,ll upper)
{
// (now) value is a part of products
if(v[id] > upper || id == v.size()) {
// std::cout << "now="<< now << '\n';
//ll sum = 0;
// if(lim==1e12) {
// std::cout << "id=" << id << '\n'; // 546
// }
for(ll x = now ; x <= limit ; x *= 2LL) {
for(ll y = 1 ; x*y <= limit ; y *= 3LL) {
for(ll z = 1 ; x*y*z <= limit; z *= 5LL) {
ans += (int)(x*y*z); //a little bug , need to change ll into interger
// sum += (int)(x*y*z);
// std::cout << "cal=" << (x*y*z) << '\n';
}
}
}
// std::cout <<"sum=" << sum << '\n';
return;
}
dfs(id + 1, now, upper);
dfs(id + 1, now * v[id], upper / v[id]);
}
int main(int argc, char const *argv[]) {
for(ll x = 1; x <= limit; x *= 2LL) {
for(ll y = 1; x*y <= limit; y *= 3LL) {
for(ll z = 1 ; x*y*z <= limit; z *= 5LL) {
// if n is a prime, call it "good" prime
// phi(n) = n - 1 = 2 ^ k_1 * 3^k_2 * 5^k_3
// ==> n = 2 ^ k_1 * 3^k_2 * 5^k_3 + 1
if(isprime(x*y*z + 1)) {
// 2 ^ k_1 * 3^k_2 * 5^k_3 + 1
v.push_back(1LL*(x*y*z + 1));
}
}
}
}
sort(v.begin(),v.end());
// std::cout << "size=" << v.size() << '\n';
// std::cout << "finish!" << '\n';
// std::cout << '\n';
// 3LL means that Skip 2, 3, 5
dfs(3LL,1LL,limit);
ans = ans % (1LL<<32);
std::cout << ans << '\n';
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
return 0;
}
转载于:https://www.cnblogs.com/LzyRapx/p/8313492.html
