问题描述:
林记在做数学习题的时候,经常遇到这种情况:苦思冥想了很久终于把问题解出来,结果发现答案是0,久而久之林记在得到习题答案是0的时候就没有了做出一道难题的成就感。于是林记决定:以后出题,答案一定不能是0,例如求n!最低位非零数这样的习题就很不错了。
现在林记提出了一个更难一点的问题:求n!在K进制下的最低位非零数。其中K符合一些特殊的条件:K是由若干个互不相同的质数相乘得出来的,例如K=2,3,5,6,7,10……
输入格式:
首先输入的第一行是一个整数Q,表示询问的个数。
接下来是Q个询问,每个询问有两行组成,第一行首先是一个整数nk,然后紧跟着nk个正整数:m1,m2,……mnk,则K为所有mi的乘积,输入保证mi是有若干个互不相同的质数相乘得出来的。接下来一行给出一个整数n。
输出格式:
对于每个询问,如果K不符合题目限制,则输出“I hate zero.”(不用加双引号)。否则输出K进制下n!的最低位非零数。
输入样例:
输出样例:
3
1 17
9
1 6
49
1 93
16
15
2
78
数据范围:
对于10%的数据满足:n≤10,K≤100
对于50%的数据满足:n≤100000,K≤100
对于100%的数据满足:n≤1015,K≤1015,mi≤106,Q≤20
【分析】
快速求阶乘大法!!
下面某步还用到 威尔逊定理 (p-1)!%p=p-1...... (也可以预处理出来的)
把m分解质因数,对于质数p单独求n!=p^a+b的a的值和b%p的值(logn递归搞定),然后用中国剩余定理合并起来。
long long的乘积会爆,所以...要用那个不断乘2的方法:
LL mul(LL x,LL y,LL p)
{
if(x==0||y==0) return 0;
LL now=x,yy=y,add=0;
while(yy>1)
{
if(yy%2!=0) add=(add+now)%p;
now=(now*2)%p;
yy/=2;
}
return (now+add)%p;
}
代码如下:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define Maxn 1000010
#define INF 0xfffffff
#define LL long long LL nk,m[Maxn],ml,K;
LL n;
LL prime[Maxn],pl;
bool q[Maxn];
LL mn; LL mymin(LL x,LL y) {return x<y?x:y;} void get_pri(LL mx)
{
pl=;
memset(q,,sizeof(q));
for(LL i=;i<=mx;i++)
{
if(q[i]) prime[++pl]=i;
for(int j=;j<=pl;j++)
{
if(i*prime[j]>mx) break;
q[i*prime[j]]=;
if(i%prime[j]==) break;
}
}
} bool div(LL mm)
{
for(LL i=;prime[i]*prime[i]<=mm;i++) if(mm%prime[i]==)
{
m[++ml]=prime[i];
mm/=prime[i];
while(mm%prime[i]==) return ;
}
if(mm!=) m[++ml]=mm;
return ;
} bool init()
{
ml=;
scanf("%lld",&nk);
K=;
bool ok=;
for(int i=;i<=nk;i++)
{
LL mm;
scanf("%lld",&mm);K*=mm;
if(!div(mm)) ok=;
}
sort(m+,m++ml);
for(LL i=;i<=ml;i++) if(m[i]==m[i-]) {ok=;break;}
scanf("%lld",&n);
if(!ok) return ;
return ;
} LL f[Maxn]; struct node{LL x,y;};
node c[Maxn]; node ffind(LL x,LL p)
{
node ans;
if(x<p)
{
ans.x=;
ans.y=f[x];
return ans;
}
ans.x=;ans.y=;
node t=ffind(x/p,p);
ans.x+=t.x; ans.y*=t.y;
ans.y=(ans.y*f[x%p])%p;
ans.x+=x/p; LL y=(((x/p)%)==)?:p-;
ans.y=(ans.y*y)%p; return ans;
} LL mul(LL x,LL y,LL p)
{
if(x==||y==) return ;
LL now=x,yy=y,add=;
while(yy>)
{
if(yy%!=) add=(add+now)%p;
now=(now*)%p;
yy/=;
}
return (now+add)%p;
} LL qpow(LL x,LL b,LL p)
{
LL ans=;
while(b)
{
if(b&) ans=mul(ans,x,p);
x=mul(x,x,p);
b>>=;
}
return ans;
} LL d[Maxn]; LL get_ans()
{
mn=c[].x;
for(LL i=;i<=ml;i++) mn=mymin(mn,c[i].x);
for(LL i=;i<=ml;i++)
{
if(c[i].x>mn) {d[i]=;continue;}
LL bm=qpow(K/m[i],mn,m[i]);
bm=qpow(bm,m[i]-,m[i]);
d[i]=mul(bm,c[i].y,m[i]);//(bm*c[i].y)%m[i];
}
LL ans=;
for(LL i=;i<=ml;i++)
{
LL y=qpow(K/m[i],m[i]-,m[i]);
//ans=(ans+((K/m[i]*y)%K)*d[i])%K;
ans=(ans+mul(mul(K/m[i],y,K),d[i],K))%K;
}
return ans;
} int main()
{
get_pri();
int T;
scanf("%d",&T);
while(T--)
{
if(!init()) {printf("I hate zero.\n");continue;}
for(LL i=;i<=ml;i++)
{
f[]=;
for(LL j=;j<m[i];j++) f[j]=(f[j-]*j)%m[i];
c[i]=ffind(n,(LL)m[i]);
}
printf("%lld\n",get_ans());
}
return ;
}
2016-09-04 19:37:26
【GDOI 2011 DAY2 T3】零什么的最讨厌了 (快速求阶乘、中国剩余定理)的更多相关文章
-
【NOIP 2017】Day2 T3 列队
Problem Description \(Sylvia\) 是一个热爱学习的女孩子. 前段时间,\(Sylvia\) 参加了学校的军训.众所周知,军训的时候需要站方阵. \(Sylvia\) 所在的 ...
-
数论-质数 poj2689,阶乘分解,求阶乘的尾零hdu1124, 求尾零为x的最小阶乘
/* 要求出[1,R]之间的质数会超时,但是要判断[L,R]之间的数是否是素数却不用筛到R 因为要一个合数n的最大质因子不会超过sqrt(n) 所以只要将[2,sqrt(R)]之间的素数筛出来,再用这 ...
-
【BZOJ 4518】【SDOI 2016 Round1 Day2 T3】征途
比较明显的斜率优化DP,省选时因为时间太紧张和斜率DP写得不熟等原因只写了60分的暴力DP,其实当时完全可以对拍来检验标算的正确,但是我当时too naive- 很快打完了,调了将近一晚上QAQ,因为 ...
-
【NOIP 2013 DAY2 T3】 华容道(spfa)
题目描述 [问题描述] 小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次.于是,他想到用编程来完成华容道:给定一种局面, 华容道是否根本就无法完成,如果能完成, 最少需要多少时间. 小 ...
-
【NOIP 2015 DAY2 T3】 运输计划 (树链剖分-LCA)
题目背景 公元 2044 年,人类进入了宇宙纪元. 题目描述 L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球. 小 P 掌管一家 ...
-
【NOIP2015提高组】 Day2 T3 运输计划
题目描述 L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球. 小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如: ...
-
一道搜索题【2013 noip提高组 DAY2 t3】华容道
这篇不多说,具体的解释都在程序里 题目描述 [问题描述] 小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次.于是,他想到用编程来完成华容道:给定一种局面, 华容道是否根本就无法完成,如果 ...
-
【NOIP 2015】Day2 T3 运输计划
Problem Background 公元 \(2044\) 年,人类进入了宇宙纪元. Description 公元\(2044\) 年,人类进入了宇宙纪元. $L $国有 \(n\) 个星球,还有 ...
-
【NOIP 2016】Day2 T3 愤怒的小鸟
Problem Description \(Kiana\) 最近沉迷于一款神奇的游戏无法自拔. 简单来说,这款游戏是在一个平面上进行的. 有一架弹弓位于 \((0,0)\) 处,每次 \(Kiana\ ...
随机推荐
-
Xcode找不到模拟器出现";My Mac";
问题如图: 步骤一. 找到target->built settings->Architectures->Base SDK, 选择你需要的版本;如果还是不行,看步骤二. 步骤二. 1) ...
-
JavaScript-日期格式化(一)
/** * 日期格式化, * @param date 要格式化的日期 * @param pattern 进行格式化的模式 * 支持的模式字母有: * y:年, * M:年中的月份(1-12), * d ...
-
Understanding Convolutions【转】
Understanding Convolutions In a previous post, we built up an understanding of convolutional neural ...
-
Debian 中添加ppa
在Debian8中默认没有"apt-add-repository"命令,所有也就没法安装ppa. 怎么破? sudo apt-get install software-proper ...
-
每日一“酷”之pprint
pprint – 美观打印 作用:美观打印数据结构 pprint 包含一个“美观打印机”,用于生成数据结构的一个美观视图.格式化工具会生成数据结构的一些表示,不仅可以由解释器正确地解析,而且便于人类阅 ...
-
OpenSSL重大漏洞-Heartbleed之漏洞利用脚本POC讲解
OpenSSL Security Advisory [07 Apr 2014] ======================================== TLS heartbeat read ...
-
依据 smtp协议的简单golang 的发邮件实现
依据 smtp协议的简单golang 的发邮件实现 协议格式如下 From:sender_user@demo.net To:to_user@demo.net Subject:这是主题 Mime-Ver ...
-
使用faker 生成中文测试数据
https://github.com/fzaninotto/Faker/blob/master/src/Faker/Provider/zh_CN/Address.php 常用的类型都在里面. 下面是一 ...
-
利用python发送邮件
找了很多使用python发送邮件的文章, 发现写的并不是太全, 导致坑特别多, 刚把这个坑跨过去, 在此记录下来 本代码使用163作为发送客户端, 接收邮箱随意 首先登录163邮箱, 开启POP3/S ...
-
js中判断undefined类型
typeof 运算符返回一个用来表示表达式的数据类型的字符串.可能的字符串有:"number"."string"."boolean".&qu ...