KIDx的解题报告
题目链接:http://poj.org/problem?id=1091
假设卡片上标号分别是a1, a2, ..., an, M,跳蚤跳对应号的次数分别为x1, x2, ..., xn,跳M个单位长度的次数是xn+1,那么要满足已知条件只需满足方程:
a1x1+a2x2+...+anxn+Mxn+1 = 1 有解,即:
gcd (a1, a2, ..., an, M) = 1,接下来对M进行素因子分解,然后排除公因子非1的情况即可。
如代码所示:
设g为公因子非1的情况数,f(i)表示有i个公因子的情况数,由容斥原理得:g = f(1) - f(2) + f(3) -... f(k)
#include <iostream>
using namespace std;
#define LL __int64
int fac[35], k, a[20], n, m, x;
LL tp;
LL my_pow (LL a, int b) //计算a^b
{
LL res = 1;
while (b--) res *= a;
return res;
}
void dfs (int pos, int cnt, int num) //dfs得到卡片中n+1个数有num个公因子时的方法数
{
if (cnt == num)
{
x = m;
for (int i = 0; i < cnt; i++)
x /= a[i]; //x/p表示[1,x]中有多少个数是p的倍数
tp += my_pow (x, n); //要选n个数,每个数有x种选择
return ;
}
for (int i = pos; i < k; i++)
{
a[cnt] = fac[i];
dfs (i+1, cnt+1, num);
}
}
void divide (int p) //分解素因子,fac存放p的所有素因子
{
for (int i = 2; i * i <= p; i++)
{
if (p % i == 0)
{
fac[k++] = i;
p /= i;
while (p % i == 0)
p /= i;
}
}
if (p > 1) fac[k++] = p;
}
int main()
{
LL ans, g;
int i;
while (cin >> n >> m)
{
g = 0;
divide (m);
for (i = 1; i <= k; i++) //g = f(1)-f(2)+f(3)-f(4)+...f(k)
{
tp = 0;
dfs (0, 0, i);
if (i & 1) g += tp;
else g -= tp;
}
ans = my_pow (m, n) - g; //ans = m^n - g
cout << ans << endl;
}
return 0;
}
分享到:
相关推荐
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
数论讲义和数论pdf,从网上找到的教材,觉得还不错,希望对大家有帮助
关于容斥原理的非常详细的讲解,+卷积+莫比乌斯反演+积性函数前缀和+集合卷积变换
容斥原理与莫比乌斯函数.md
@cfannet.com@初等数论+I(陈景润).pdf [算法数论].裴定一.清晰版.pdf 基础数论_杜德利.pdf 数论基础_张君达编.pdf
数学概貌丛书++数论概貌(陈景润).pdf
poj上一些题目的代码。都是自己平时做的一些题。拿出来用于交流。这些代码见证了从最初只会写a+b到半年前的一个过程。
一-BASIC 3 IO挂 3 快速乘法 3 快速幂 3 进制转换(包括负进制)概念 3 一个数二进制1的个数 3 二-整除问题 3 整除具有的性质 3 gcd和lcm 3 一般gcd 3 快速gcd 4 扩展gcd 4 ...筛1~n的因子个数O(n) 10
本书为潘承洞院士写的初等数论的入门读物,每章后都有大量的习题供读者练习。
希尔伯特1897年向德国数学会提交的《数论报告》用新的统一的观点,将以往代数数论的知识熔为一个整体。他抓住了互反律这个中心,利用范数剩余记号将高斯古典互反律表示成简单优美的形式: ,从而猜测到高斯互反律的...
这是一个初步介绍数论知识的课件 这是一个真正数论的开始
数论讲义, 数论是纯粹数学的分支之一,主要研究整数的性质。整数可以是方程式的解(丢番图方程)。有些解析函数(像黎曼ζ函数)中包括了一些整数、质数的性质,透过这些函数也可以了解一些数论的问题。透过数论也...
哈代数论本书是数论领域的一部传世名著,成书于作者在牛津大学、剑桥大学等学校授课的讲义。书中从各个不同角度对数论进行了阐述,内容包括素数、无理数、同余、费马定理、连分数、不定式、二次域、算术函数、分化等...
ACM+数论常用的模版
经典初等数论例题100例以及初等数论定理的证明
根据颜远松《计算数论》一书,本书为计算机信息安全专业的必修课程,本门课程有大量晦涩难懂的算法,计算量大,特别集中在2.3节大整数分解和2.4节离散对数两章,本应用实现并集成了大整数分解的5个算法和离散对数的...
潘氏兄弟继《初等数论》、《代数数论》之后的又一大倾力贡献,是数论爱好者的必修之课。
这是一套完整的数论学习教材,可供C++数论初学者学习,里面内容丰富,通俗易懂。
学习数论,算法分析的必备知识,快下载初等数论