题意:规定每次跳的单位 a1, a2, a3 …… , an, M,次数可以为b1, b2, b3 …… bn, bn + 1, 正好表示往左,负号表示往右, 求能否调到左边一位,即 a1* b1+ a2 * b2 + a3 * b3 + …… + m * (bn + 1) = 1;
根据欧几里得,则a1, a2 a3 …… an, m 最大公约数为1,m已知且a1, a2, a3 …… an 均小于等于m, 一共有m ^ n可能, 将m 唯一分解之后, 假设m = 2 * 3 * 5, 则不大于m且包含2因子的 共 m / 2, 包含3的 为 m/ 3, 容斥
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;
const int Max = + ;
typedef long long LL;
LL n, m;
int prime[Max + ], vis[Max + ], tot;
LL em[], a[], cnt;
LL res;
void getPrime()
{
tot = , cnt = ;
memset(vis, , sizeof(vis));
for (int i = ; i <= Max; i++)
{
if (!vis[i])
{
prime[tot++] = i;
for (int j = i; j <= Max / i; j++)
vis[i * j] = ;
}
} }
void getfactor(int b)
{
memset(em, , sizeof(em));
for (int i = ; i < tot; i++)
{
if (prime[i] > b)
break;
if (b % prime[i] == )
{
em[cnt++] = prime[i];
while (b % prime[i] == )
{
b /= prime[i];
}
}
}
if (b > )
em[cnt++] = b;
}
LL Pow(LL a, LL b)
{
LL ans = ;
while (b > )
{
if (b & )
ans *= a;
b >>= ;
a *= a;
}
return ans;
}
void dfs(int cur, int num, int Cnt) // cur当前位置, num当前已包含个数,Cnt目标个数
{
if (num == Cnt)
{
//达到目标个数时, 用 m 去除以 所有包含的数
LL u = m;
for (int i = ; i < num; i++)
u /= a[i];
res += Pow(u, n);
return;
}
for (int i = cur; i < cnt; i++)
{
a[num] = em[i];
dfs(i + , num + , Cnt);
}
return;
}
int main()
{
getPrime();
while (scanf("%I64d%I64d", &n, &m) != EOF)
{
getfactor(m);
LL sum = Pow(m, n);
for (int i = ; i <= cnt; i++) // 枚举每一个组合,i表示每个组合中数的个数
{
res = ;
dfs(, , i);
if (i & )
sum -= res;
else
sum += res;
}
printf("%I64d\n", sum);
} return ;
}
POJ1091跳蚤(容斥 + 唯一分解 + 快速幂)的更多相关文章
-
HUST 1569(Burnside定理+容斥+数位dp+矩阵快速幂)
传送门:Gift 题意:由n(n<=1e9)个珍珠构成的项链,珍珠包含幸运数字(有且仅由4或7组成),取区间[L,R]内的数字,相邻的数字不能相同,且旋转得到的相同的数列为一种,为最终能构成多少 ...
-
2017ACM暑期多校联合训练 - Team 8 1011 HDU 6143 Killer Names (容斥+排列组合,dp+整数快速幂)
题目链接 Problem Description Galen Marek, codenamed Starkiller, was a male Human apprentice of the Sith ...
-
bzoj 3930: [CQOI2015]选数【快速幂+容斥】
参考:https://www.cnblogs.com/iwtwiioi/p/4986316.html 注意区间长度为1e5级别. 则假设n个数不全相同,那么他们的gcd小于最大数-最小数,证明:则gc ...
-
刷题总结——跳蚤(poj1091容斥+分解质因数)
题目: Description Z城市居住着很多只跳蚤.在Z城市周六生活频道有一个娱乐节目.一只跳蚤将被请上一个高空钢丝的正*.钢丝很长,可以看作是无限长.节目主持人会给该跳蚤发一张卡片.卡片上写有 ...
-
BZOJ 1008--[HNOI2008]越狱(容斥&;快速幂)
1008: [HNOI2008]越狱 Time Limit: 1 Sec Memory Limit: 162 MBSubmit: 12593 Solved: 5439[Submit][Status ...
-
[HNOI2002]跳蚤 【容斥】
题目描述 Z城市居住着很多只跳蚤.在Z城市周六生活频道有一个娱乐节目.一只跳蚤将被请上一个高空钢丝的正*.钢丝很长,可以看作是无限长.节目主持人会给该跳蚤发一张卡片.卡片上写有N+1个自然数.其中最 ...
-
hdu 5768 Lucky7 中国剩余定理+容斥+快速乘
Lucky7 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Problem D ...
-
HDU 5768Lucky7(多校第四场)容斥+中国剩余定理(扩展欧几里德求逆元的)+快速乘法
地址:http://acm.hdu.edu.cn/showproblem.php?pid=5768 Lucky7 Time Limit: 2000/1000 MS (Java/Others) M ...
-
【GDOI2016模拟3.16】幂(容斥 + 模型复杂转化)
[GDOI2016模拟3.16]幂 \(X\in[1,A],Y\in[1,B]\),问:\(x^y\)的不用取值个数. \(A,B\)都是\(10^9\)级别. 然后我们开搞. 首先,假设一个合法的\ ...
随机推荐
-
VS2013_QT255开发相关技巧理解心得
1. 在VS2013中打开QTCreater新建的项目 (1)通过双击.ui 打开QT的设计器,然后修改. (2)通过QT设计器,新建ui文件,放在VSQT的工程中 但是需要对此xxx.ui文件,进行 ...
-
UDP socket 设置为的非阻塞模式
UDP socket 设置为的非阻塞模式 Len = recvfrom(SocketFD, szRecvBuf, sizeof(szRecvBuf), MSG_DONTWAIT, (struct so ...
-
《深入浅出嵌入式底层软件开发》—1. ARM汇编编程基础
1.1 ARM CPU寄存器 ARM的汇编编程,本质上就是针对CPU寄存器的编程,所以要搞清楚ARM有哪些寄存器:ARM寄存器分为两类:普通寄存器和状态寄存器:普通寄存器一共有16个,分别为R0——R ...
-
情人节,教大家使用css画出一朵玫瑰花。
情人节到了,给大家来一朵高端的玫瑰花. 在网上看到的一个canvas实现的玫瑰花,效果很好,但是代码被压缩过,也没有注释,看的云里雾里的. 今天我教大脚用CSS来实现一朵玫瑰花. 先看效果 首先我们画 ...
-
MFS文件系统的组成
1. 元数据服务器.在整个体系中负责管理管理文件系统,目前MFS只支持一个元数据服务器master,这是一个单点故障,需要一个性能稳定的服务器来充当.希望今后MFS能支持多个master服务器,进一 ...
-
Java爬虫——B站弹幕爬取
如何通过B站视频AV号找到弹幕对应的xml文件号 首先爬取视频网页,将对应视频网页源码获得 就可以找到该视频的av号aid=8678034 还有弹幕序号,cid=14295428 弹幕存放位置为 h ...
-
[Swift]LeetCode272. 最近的二分搜索树的值 II $ Closest Binary Search Tree Value II
Given a non-empty binary search tree and a target value, find k values in the BST that are closest t ...
-
Deep Convolution Auto-encoder
一.概念介绍 自编码器是一种执行数据压缩的网络架构,其中的压缩和解压缩功能是从数据本身学习得到的,而非人为手工设计的.自编码器的两个核心部分是编码器和解码器,它将输入数据压缩到一个潜在表示空间里面,然 ...
-
docker 启动报错 WARNING: IPv4 forwarding is disabled. Networking will not work.
解决办法: # vi /etc/sysctl.conf 或者 # vi /usr/lib/sysctl.d/00-system.conf 添加如下代码: net.ipv4.ip_forward ...
-
Jquery里的特定小技巧
jQuery 动态设置样式: https://blog.csdn.net/xiaoyuncc/article/details/70854925 jquery如 ...