fsums.cpp

#include <iostream>
#include <cmath>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <sstream>
#include <algorithm>
#include <array>
#include <cassert>
#include <cstdio>
#include  <cstdint>

using namespace std;
using Int = int64_t;
struct frac{
	Int n;
	Int d;
	bool operator < (frac other){
		return other.d * n < d * other.n;
	//	return n/double(d) < other.n/double(other.d); 
	}
};
constexpr size_t max_n = 10000+1;
vector<frac> flist;

vector<Int> primes;
vector<unordered_set<Int>> num_ps(max_n);
void calc_primes(){
	bool prime[max_n];
	for(int i = 0; i < max_n; i++)
		prime[i] = true;
	for(int i = 2; i < max_n; i++){
		if(prime[i]){
			for(int j = i*2; j < max_n; j += i){
				prime[j] = false;
				num_ps[j].insert(i);
			}
			primes.push_back(i);
		}
	}
}
bool are_coprime(int a,int b){
	if(num_ps[b].count(a)){
		return false;
	}
	for(Int p : num_ps[a]){
		if(num_ps[b].count(p)){
			return false;
		}
	}
	return true;
}
void calc_list(){
	size_t idx = 0;
	flist.push_back(frac{1,1});
	flist.push_back(frac{0,1});
	for(int b = 1; b < max_n; b++){
		for(int a = 1; a < b; a++){
			if(are_coprime(a,b)){
				flist.push_back(frac{a,b});
			}
		}
	}
	sort(flist.begin(),flist.end());
	cout << flist.size() << endl;
}
Int outs[max_n];
void calc_outs(){
	//vector<vector<Int>> counts(max_n);
	cout << "[";
	for(int i = 2; i < max_n; i++){
		Int counts[max_n];
		for(int k = 0; k < max_n; k++) counts[k] = 0;
		
		Int dbef = -1;
		for(frac f : flist){
			if(f.d <= i){
				Int curd = f.d;
				if (dbef != Int(-1)){
					counts[curd] += dbef;
				}
				dbef = curd;
			}
		}
		Int sum = 0;
		for(int j = 1; j < max_n; j++){
			int num = j;
			assert((2*counts[j]) % num == 0);
			sum += (2*counts[j]) / num;
		}
		cout << sum << ",";
		outs[i] = sum;
	}
	cout << "]\n";
}
int main(){
	calc_primes();
	calc_list();
	
	calc_outs();
	return 0;
}