Playground
#include <iostream> #include <vector> #include <string> using namespace std; vector<int> find_prime_divisors(int N) { vector<int> divisors; //se dvizhime do kvadratniot koren na N (i <= sqrt(N)) = (i*i <= N) //bidejki ako ima delitel pogolem od sqrt(N), //togash postoi i pomal delitel, pa toj kje go najdeme prvo for (int i=2; i*i <= N; i++) { if ((N%i) == 0) { divisors.push_back(i); //najdovme delitel, nema potreba da go dodavame istiot povekje pati while ((N%i) == 0) { N /= i; } } } //mozhebi prost broj ostanal vo N, ili N bil prost broj na pochetokot? if (N >= 2) { divisors.push_back(N); } return divisors; } //brojot na elementi vo edno mnozhestvo mozhe da se presmeta //kako brojot na bitovi ednakvi na 1 int elements_in_subset(int subset) { int one_bits = 0; //izminuvaj go brojot bit po bit... //delenjeto so 2 go brishe posledniot bit while (subset > 0) { if ((subset % 2) == 1) { one_bits++; } subset /= 2; } return one_bits; } int calculate(int N, int M) { vector<int> divisors = find_prime_divisors(M); int divisors_count = divisors.size(); int bad_numbers_count = 0; //gi razgleduvame site podmnozhestva - takvi postojat 2^(divisors_count) //pochnuvame od i=1, bidejki ne ne interesira praznoto podmnozhestvo []. for (int i=1; i < (1 << divisors_count); i++) { int product = 1; //proizvod na elementite vo podmnozhestvoto //za da znaeme kolku da dodademe ili odzememe. //na primer, za "deliv so 2" i "deliv so 3", imame product=2*3 for (int j=0; j < divisors_count; j++) { if ((i & (1 << j)) != 0) { //vo proizvodot vleguvaat onie vrednosti koi se del //od podmnozhestvoto definirano so "i" product *= divisors[j]; } } //kolku vrednosti ima vo presekot, na primer //ako N=20, togash ima 20/6=3 broevi delivi i so 2 i so 3. int number_of_values = (N / product); if ((elements_in_subset(i) % 2) == 1) { //ako ima neparen broj na elementi, dodavame bad_numbers_count += number_of_values; } else { //ako ima paren broj na elementi, odzemame bad_numbers_count -= number_of_values; } } return (N - bad_numbers_count); } int main() { int N, M; cin >> N >> M; cout << calculate(N, M) << endl; return 0; }
Input data
Program output
20 6
Execute
Language: ????????? | Memory: ???? KB | Time: ??? ms
Nothing has been executed, yet!