题目链接:Codeforces 439E Devu and Birthday Celebration
题目大意:给出q,表示询问的次数,每次询问有n和f,问有多少种分类方法,将n分成f份,并且这f份的最大共约数为1.
解题思路:如果不考虑说最大共约数为1的话,那么问题很简单,就是f个数的和为n的种数C(f−1n−1).所以我们就尽量将问题转化成说f数的和为s的子问题。用容斥原理,总的可能减去公约数不为1的情况,那么公约数不为1的情况就去枚举公约数。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
const int MOD = 1e9+7;
vector<int> vec;
int fact[N], ive_fact[N];
int power (int x, int n) {
int ans = 1;
while (n) {
if (n&1)
ans = (1ll * ans * x) % MOD;
n /= 2;
x = (1ll * x * x) % MOD;
}
return ans;
}
void init () {
fact[0] = 1;
for (int i = 1; i < N; i++)
fact[i] = (1ll * fact[i-1] * i) % MOD;
for (int i = 0; i < N; i++)
ive_fact[i] = power(fact[i], MOD-2);
}
void divFactor(int cur) {
vec.clear();
int tmp = sqrt(cur+0.5);
for (int i = 2; i <= tmp; i++) {
if (cur % i == 0) {
vec.push_back(i);
while (cur % i == 0)
cur /= i;
}
}
if (cur != 1)
vec.push_back(cur);
}
int solve (int n,int f) {
if (n < f)
return 0;
int ans = fact[n];
ans = 1ll * ans * ive_fact[f] % MOD;
ans = 1ll * ans * ive_fact[n-f] % MOD;
return ans;
}
int cal (int n) {
return (n % MOD + MOD) % MOD;
}
int main () {
init();
int cas;
scanf("%d", &cas);
while (cas--) {
int n, f;
scanf("%d%d", &n, &f);
divFactor(n);
int ans = 0, t = 1<<vec.size();
for (int i = 0; i < t; i++) {
int tmp = 1, sign = 1;
for (int j = 0; j < vec.size(); j++) {
if (i&(1<<j)) {
sign *= -1;
tmp *= vec[j];
}
}
ans = cal(ans + sign * solve(n/tmp - 1, f - 1));
}
printf("%d\n", ans);
}
return 0;
}
分享到:
相关推荐
Codeforces - 1131C. Birthday(贪心)题目链接题目给你n和n个数,要你重新排列n个数,使得这些数的相邻差值中最大的那个值最小。stat
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
题目大意:给出一个由 n 个点组成的树,现在可以询问 n/2 次(向下取整)LCA,确定根节点是哪个节点 题目分析:因为最多只能求 n/2 次lca,每次需要两个节点作为参数,也就是说每个点我们至多遍历一遍,读完题后没什么...
题意: 给出 nnn 个点,n−1n-1n−1 条边,最多询问 n2\frac{n}{2}2n 次,每次询问 u,vu,vu,v,会给出 uvuvuv的最近公共祖先,求树的根。 ...操作就是一个删除叶子节点的过程。 AC代码: const int N = 1010;...
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
E. Array Shrinking time limit per test2 seconds memory limit per test256 megabytes inputstandard input outputstandard output You are given an array a1,a2,…,an. You can perform the following operation...
PDF-CodeForces问题 PDF文件中的CodeForces问题 利用CodeForces提取在这个库中的文件 ,文件夹名代表来自CodeForces网址contests`的ID,每个文件夹包含比赛的问题。 有关CodeForces竞赛的疯狂事实 CodeForces上有937...
Codeforces global round 10 codes
题目大意:给出 n 个数字组成的序列,现在可以对数列进行多次操作,每次操作可以选择其中一段连续的数列,用其平均数替换原位置,换句话说,若原连续数列为 1 2 3,则可以替换为 2 2 2,问如何操作可以使得最后答案...
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
Codeforces问题
CodeForces 适用于问题的Python解决方案。 用户名: hopper19
解决问题的方法教育Codeforces回合101 - 2/6 常规托架顺序-接受红色和蓝色-接受Codeforces回合#686(Div.3) 2/6 特殊排列-接受唯一出价拍卖-接受序列转换-接受编号成序列-接受Codeforces回合#685(分区2) 2/7 减...