Skip to content

Instantly share code, notes, and snippets.

@LiTianxiong LiTianxiong/p.cpp Secret
Created Mar 23, 2020

Embed
What would you like to do?
1234
// 10s, 500MB
/// ans = 462
#include <iostream>
#include <algorithm>
#include <vector>
#include <thread>
#include <ctime>
using namespace std;
typedef unsigned int ull;
const ull thread_num = 20;
const ull maxn = 100000000;
ull prime[maxn/10];
bool is_prime[maxn+1] = {0};
ull cache[maxn+1] = {0};
ull getprime(ull n)
{
ull tot = 1;
prime[0] = 2;
is_prime[2] = true;
for(ull i=3; i<=n; i+=2) is_prime[i] = true;
for(ull i=3; i<=n; i+=2)
{
if(is_prime[i]) prime[tot++] = i;
for(ull j=1; j<tot && prime[j]*i<=n; j++)
{
is_prime[i*prime[j]] = false;
if(i%prime[j] == 0) break;
}
}
return tot;
}
ull getSumOfDivisors(ull n)
{
if(n < 4) return 1;
ull ans = 1;
size_t i = 0;
while(i<maxn)
{
ull p = prime[i++];
if(n%p == 0)
{
ull t = p*p;
n /= p;
while(n%p == 0)
{
t *= p;
n /= p;
}
ans *= (t-1) / (p-1);
}
if(p*p > n) break;
}
if(n > 1) ans *= n+1; // (n^2-1)/(n-1) = ((n+1)(n-1))/(n-1) = n+1
return ans;
}
ull d(ull n)
{
if(cache[n]) return cache[n];
else return cache[n] = getSumOfDivisors(n) - n;
}
void run(ull l, ull r, vector<pair<ull, ull>> & ans)
{
for(ull i=l; i<r; ++i)
{
ull t = d(i);
if(t<=maxn && t!=i && d(t)==i)
{
ans.push_back({i, t});
// cout << t << " " << i << endl;
}
}
}
int main()
{
auto start = clock();
getprime(maxn);
vector<thread> threads;
vector<pair<ull, ull>> ans[thread_num];
for (ull i = 0; i < thread_num; ++i)
{
ull l = 4 + i * (maxn / thread_num),
r = l + (maxn / thread_num);
if (i == thread_num - 1)
r = maxn + 1;
threads.push_back(move(thread(
run,
l, r, ref(ans[i]))));
}
for (auto &ite : threads)
ite.join();
int count = 0;
for(auto &ite : ans) count += ite.size();
// for(auto &ite : ans)
// {
// for(auto &p : ite) cout << p.first << " " << p.second << endl;
// }
cout << "count: " << count << endl;
cout << clock() - start << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.