verify/spoj/spoj-FACT0.test.cpp

View this file on GitHub
Last update: 2022-07-21 16:12:33-04:00
Problem: https://www.spoj.com/problems/FACT0/

Depends on

Code

#define PROBLEM "https://www.spoj.com/problems/FACT0/"

#include "../../library/contest/template-minimal.hpp"
#include "../../library/number-theory/basic-factor.hpp"

// verified probably using SPOJ?

int main() {
	using namespace FactorBasic;
	using namespace std;
	while (true) {
		long long n;
		cin >> n;
		if (n == 0) return 0;
		auto f = factor(n);
		for (auto x : f) {
			cout << x.first << "^" << x.second << " ";
		}
		cout << '\n';
	}  
	return 0;
}

#define PROBLEM "https://www.spoj.com/problems/FACT0/"


#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <iostream>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

namespace FactorBasic {

template <class T> std::vector<std::pair<T, int>> factor(T x) {
	std::vector<std::pair<T, int>> pri;
	for (T i = 2; i * i <= x; ++i) {
		if (x % i == 0) {
			int t = 0;
			while (x % i == 0) x /= i, t++;
			pri.push_back({i, t});
		}
	}
	if (x > 1) pri.push_back({x, 1});
	return pri;
}

template <class T> T phi(T x) {
	for (auto& a : factor(x)) x -= x / a.first;
	return x;
}

template <class T> void tour(std::vector<std::pair<T, int>>& v, std::vector<T>& res, int ind, T cur) {
	if (ind == (int)v.size()) res.push_back(cur);
	else {
		T mul = 1;
		for (int i = 0; i < v[ind].second + 1; i++) {
			tour(v, res, ind + 1, cur * mul);
			mul *= v[ind].first;
		}
	}
}

template <class T> std::vector<T> get_divisor(T x) {
	auto v = factor(x);
	std::vector<T> res; 
	tour(v, res, 0, (T) 1);
	sort(res.begin(), res.end());
	return res;
}

}

// verified probably using SPOJ?

int main() {
	using namespace FactorBasic;
	using namespace std;
	while (true) {
		long long n;
		cin >> n;
		if (n == 0) return 0;
		auto f = factor(n);
		for (auto x : f) {
			cout << x.first << "^" << x.second << " ";
		}
		cout << '\n';
	}  
	return 0;
}