Submission 829 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
829	15/05/2013 22:49:27	leandro	D - El día del Divino Byte	Accepted	16	1.4 KiB	GNU G++ 5.1.0

Code

/*
username: leandro
*/
#include <cassert>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <complex>
#include <set>
#include <map>
#include <sstream>
#include <queue>
#include <stack>

using namespace std;

//////////////////////////////////////
typedef long long i64;
typedef complex<double> pnt;
typedef pair<int, int> pii;
typedef vector<int> vi;
//////////////////////////////////////
const int oo = 1 << 30;
const double PI = M_PI;
const double EPS = 1e-15;
//////////////////////////////////////
#define F first
#define S second
#define foreach(i, u) \
		for (typeof(u.begin()) i = u.begin(); i != u.end(); i++)
#define REP(i, n) \
		for (int i = 0; i < (n); i++)
#define FOR(i, n) \
		for (int i = 1; i <= (n); i++)
//////////////////////////////////////
#define DEBUG(x) \
		cout << #x << " = " << x << endl

i64 N, M;
int size;
i64 p[ 15 ];
vector<i64> answer;

void gcd(i64 &g, i64& x, i64& y, i64 a, i64 b)
{
	if (b == 0)
	{
		g = a;
		x = 1;
		y = 0;
	}
	else
	{
		gcd(g, y, x, b, a % b);
		y = y - (a / b) * x;
	}
}

int main()
{
	cin.sync_with_stdio(false);

cin >> N >> M;

M = 2 * M;
	i64 m = M;
	for (i64 i = 2; i * i <= m; i++)
	{
		if (m % i) continue;
		p[ size ] = 1;
		while (m % i == 0)
		{
			p[ size ] = p[ size ] * i;
			m /= i;
		}
		size = size + 1;
	}

if (m > 1)
		p[ size++ ] = m;

for (int i = 0; i < (1 << size); i++)
	{
		i64 n1 = 1;
		for (int j = 0; j < size; j++)
			if (i & (1 << j)) n1 = n1 * p[j];
		i64 n2 = M / n1;

/* solve */
		i64 g, _x, _y;
		gcd(g, _x, _y, n1, -n2);

if (g == -1) //Warning here//
		{
			_x = -_x;
		}

i64 ans = -1 * _x  * n1;

/**/
		if (ans < 0)
			ans = ans + M * (labs(ans) / M + 1);
		ans = ans % M;
		/**/

answer.push_back(ans);
	}

i64 ccount = 0;
	for (int i = 0; i < (int)answer.size(); i++)
	{
		bool valid = true;
		for (int j = 0; j < i; j++)
			if (answer[i] == answer[j]) { valid = false; break; }
		if (valid)
		{
			i64 x = answer[i];
			if (x == 0)
				x = x + M;
			if (x <= N)
				ccount += (N - x) / M + 1;
		}
	}

cout << ccount << endl;

return 0;
}

Judgement Details

Test 01: 0.011 0.000 1388K ok
Test 02: 0.009 0.000 1356K ok
Test 03: 0.011 0.000 1360K ok
Test 04: 0.010 0.000 1356K ok
Test 05: 0.010 0.000 1356K ok
Test 06: 0.013 0.000 1360K ok
Test 07: 0.012 0.000 1356K ok
Test 08: 0.011 0.016 1360K ok
Test 09: 0.010 0.000 1356K ok
Test 10: 0.010 0.000 1388K ok
Test 11: 0.010 0.000 1360K ok
Test 12: 0.009 0.000 1356K ok
Test 13: 0.010 0.000 1356K ok
Test 14: 0.012 0.000 1356K ok
Test 15: 0.012 0.000 1356K ok
Test 16: 0.009 0.000 1356K ok
Test 17: 0.012 0.000 1356K ok
Test 18: 0.010 0.000 1360K ok
Test 19: 0.010 0.016 1360K ok
Test 20: 0.010 0.000 1360K ok
Accepted

Matcom Online Grader Faculty of Mathematics and Computer Science of University of Havana

Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana