Участник:Easik/FNRANK

Материал из DISCOPAL
< Участник:Easik
Версия от 01:58, 11 декабря 2020; Easik (обсуждение | вклад) (Новая страница: «* https://www.spoj.com/problems/FNRANK/ '''C \ gcc''' <code-c> #include <stdio.h> #include <stdlib.h> #define MAX_N 100001 int tot, ans; long long rnk; int NN,…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

C \ gcc

#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100001
 
int tot, ans;
long long rnk;
int NN, tt, N;
int T, n, a, b;
 
int c[MAX_N], P[MAX_N];
int p[11];
 
void dfs(int dep, int now, int cc);
 
 
int main() {
 
    int i, j;
    int x;
    int num, check;
 
	c[1] = 0;
	for (i = 2; i < MAX_N; i++) {
 
		if (!c[i]) {
 
            P[++tot] = i;
            c[i] = i;
 
        }
 
		for (j = 1; j <= tot; j++) {
 
			if ((long long)i * P[j] < MAX_N) {
 
                c[i * P[j]] = P[j];
 
            } else {
 
                break;
 
            }
 
			if (i % P[j] == 0) break;
 
		}
	}
 
	scanf("%d", &T);
 
	while (T--) {
 
		scanf("%d %d %d", &n, &a, &b);
		rnk = 0;
 
		for (i = 1; i <= n; i++) {
 
			N = (long long)i * a / b;
			num = i;
            check = 0;
			tt = 0;
 
            while (num != 1) {
 
				x = c[num];
				num /= x;
				if (x != c[num]) p[++tt] = x;
 
			}
 
            NN = 0;
			dfs(0,1,0);
			rnk += NN;
 
		}
 
		rnk++;
		printf("%lld\n", rnk);
 
	}
 
    return 0;
 
}
 
 
/* Depth-first search */
void dfs(int dep, int now, int cc) {
 
    if (dep == tt) {
 
        NN += (N / now) * ((cc % 2 == 0) ? 1 : -1);
		return;
 
	}
 
	dfs(dep + 1, now, cc);
 
	if ((long long)now * p[dep + 1] <= N) {
 
        dfs(dep + 1, now * p[dep + 1],cc + 1);
 
    }
 
}