POJ1091跳蚤(容斥 + 唯一分解 + 快速幂)

时间:2022-12-22 09:30:56
 

题意:规定每次跳的单位 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跳蚤(容斥 + 唯一分解 + 快速幂)的更多相关文章

  1. HUST 1569&lpar;Burnside定理&plus;容斥&plus;数位dp&plus;矩阵快速幂&rpar;

    传送门:Gift 题意:由n(n<=1e9)个珍珠构成的项链,珍珠包含幸运数字(有且仅由4或7组成),取区间[L,R]内的数字,相邻的数字不能相同,且旋转得到的相同的数列为一种,为最终能构成多少 ...

  2. 2017ACM暑期多校联合训练 - Team 8 1011 HDU 6143 Killer Names &lpar;容斥&plus;排列组合,dp&plus;整数快速幂&rpar;

    题目链接 Problem Description Galen Marek, codenamed Starkiller, was a male Human apprentice of the Sith ...

  3. bzoj 3930&colon; &lbrack;CQOI2015&rsqb;选数【快速幂&plus;容斥】

    参考:https://www.cnblogs.com/iwtwiioi/p/4986316.html 注意区间长度为1e5级别. 则假设n个数不全相同,那么他们的gcd小于最大数-最小数,证明:则gc ...

  4. 刷题总结——跳蚤(poj1091容斥&plus;分解质因数)

    题目: Description Z城市居住着很多只跳蚤.在Z城市周六生活频道有一个娱乐节目.一只跳蚤将被请上一个高空钢丝的正*.钢丝很长,可以看作是无限长.节目主持人会给该跳蚤发一张卡片.卡片上写有 ...

  5. BZOJ 1008--&lbrack;HNOI2008&rsqb;越狱(容斥&amp&semi;快速幂)

    1008: [HNOI2008]越狱 Time Limit: 1 Sec  Memory Limit: 162 MBSubmit: 12593  Solved: 5439[Submit][Status ...

  6. &lbrack;HNOI2002&rsqb;跳蚤 【容斥】

    题目描述 Z城市居住着很多只跳蚤.在Z城市周六生活频道有一个娱乐节目.一只跳蚤将被请上一个高空钢丝的正*.钢丝很长,可以看作是无限长.节目主持人会给该跳蚤发一张卡片.卡片上写有N+1个自然数.其中最 ...

  7. hdu 5768 Lucky7 中国剩余定理&plus;容斥&plus;快速乘

    Lucky7 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Problem D ...

  8. HDU 5768Lucky7(多校第四场)容斥&plus;中国剩余定理(扩展欧几里德求逆元的)&plus;快速乘法

    地址:http://acm.hdu.edu.cn/showproblem.php?pid=5768 Lucky7 Time Limit: 2000/1000 MS (Java/Others)    M ...

  9. 【GDOI2016模拟3&period;16】幂(容斥 &plus; 模型复杂转化)

    [GDOI2016模拟3.16]幂 \(X\in[1,A],Y\in[1,B]\),问:\(x^y\)的不用取值个数. \(A,B\)都是\(10^9\)级别. 然后我们开搞. 首先,假设一个合法的\ ...

随机推荐

  1. VS2013&lowbar;QT255开发相关技巧理解心得

    1. 在VS2013中打开QTCreater新建的项目 (1)通过双击.ui 打开QT的设计器,然后修改. (2)通过QT设计器,新建ui文件,放在VSQT的工程中 但是需要对此xxx.ui文件,进行 ...

  2. UDP socket 设置为的非阻塞模式

    UDP socket 设置为的非阻塞模式 Len = recvfrom(SocketFD, szRecvBuf, sizeof(szRecvBuf), MSG_DONTWAIT, (struct so ...

  3. 《深入浅出嵌入式底层软件开发》—1&period; ARM汇编编程基础

    1.1 ARM CPU寄存器 ARM的汇编编程,本质上就是针对CPU寄存器的编程,所以要搞清楚ARM有哪些寄存器:ARM寄存器分为两类:普通寄存器和状态寄存器:普通寄存器一共有16个,分别为R0——R ...

  4. 情人节,教大家使用css画出一朵玫瑰花。

    情人节到了,给大家来一朵高端的玫瑰花. 在网上看到的一个canvas实现的玫瑰花,效果很好,但是代码被压缩过,也没有注释,看的云里雾里的. 今天我教大脚用CSS来实现一朵玫瑰花. 先看效果 首先我们画 ...

  5. MFS文件系统的组成

    1.  元数据服务器.在整个体系中负责管理管理文件系统,目前MFS只支持一个元数据服务器master,这是一个单点故障,需要一个性能稳定的服务器来充当.希望今后MFS能支持多个master服务器,进一 ...

  6. Java爬虫——B站弹幕爬取

    如何通过B站视频AV号找到弹幕对应的xml文件号 首先爬取视频网页,将对应视频网页源码获得 就可以找到该视频的av号aid=8678034 还有弹幕序号,cid=14295428 弹幕存放位置为  h ...

  7. &lbrack;Swift&rsqb;LeetCode272&period; 最近的二分搜索树的值 II &dollar; 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 ...

  8. Deep Convolution Auto-encoder

    一.概念介绍 自编码器是一种执行数据压缩的网络架构,其中的压缩和解压缩功能是从数据本身学习得到的,而非人为手工设计的.自编码器的两个核心部分是编码器和解码器,它将输入数据压缩到一个潜在表示空间里面,然 ...

  9. docker 启动报错 WARNING&colon; IPv4 forwarding is disabled&period; Networking will not work&period;

    解决办法: # vi /etc/sysctl.conf 或者 # vi /usr/lib/sysctl.d/00-system.conf 添加如下代码:     net.ipv4.ip_forward ...

  10. Jquery里的特定小技巧

    jQuery 动态设置样式:                      https://blog.csdn.net/xiaoyuncc/article/details/70854925 jquery如 ...