这么sb的题考场居然写挂了2233。
假设n=∏iaiki" role="presentation" style="position: relative;">n=∏iakiin=∏iaiki
那么集合中合法的数一定满足:
t=∏i(1/aiki)" role="presentation" style="position: relative;">t=∏i(1/akii)t=∏i(1/aiki)
发现后面的i很小,可以状压dp一发。
然后就没了。
注意集合中有1时需要把答案乘二。
代码:
#include<bits/stdc++.h>
#define N 100005
#define first xx
#define second yy
#define ll long long
using namespace std;
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int a[505],m,tot=0,divv[N],cal[N],siz=0,dp[1<<20],sta[N];
ll n;
map<int,bool>in;
inline bool check(int x){
if(n%x)return false;
int t=sqrt(x),tmp=x;
bool f=true;
for(int i=2;i<=t;++i){
if(tmp==1)break;
if(tmp%i)continue;
while(tmp%i==0)tmp/=i;
if(!in[i])in[i]=true,divv[++siz]=i;
if(n/x%i==0)f=false;
}
if(tmp!=1&&!in[tmp])in[tmp]=true,divv[++siz]=tmp;
if(!f)return false;
if(tmp==1)return true;
if(n/x%tmp==0)return false;
return true;
}
int main(){
n=read(),m=read(),dp[0]=1;
for(int i=1;i<=m;++i){
int x=read();
if(x==1){dp[0]=2;continue;}
if(check(x))a[++tot]=x;
}
if(!tot){cout<<"0";return 0;}
sort(divv+1,divv+siz+1);
for(int i=1;i<=siz;++i){
ll tmp=n;
while(tmp%divv[i]==0)tmp/=divv[i];
}
for(int i=1;i<=tot;++i)for(int j=1;j<=siz;++j)if(a[i]%divv[j]==0)sta[i]|=1<<(j-1);
for(int i=0;i<(1<<siz);++i)for(int j=1;j<=tot;++j)
if((i&sta[j])==0&&i<sta[j])dp[i|sta[j]]+=dp[i];
cout<<dp[(1<<siz)-1];
return 0;
}
2018.09.08 NOIP模拟 division(状压dp)的更多相关文章
-
NOIP模拟 乘积 - 状压dp + 分组背包
题目大意: 给出n和k,求从小于等于n的数中取出不超过k个,其乘积是无平方因子数的方案数.无平方因子数:不能被质数的平方整除. 题目分析: 10(枚举\(n\le8\)),40(简单状压\(n\le1 ...
-
2018.09.08 NOIP模拟trip(最长链计数)
差不多是原题啊. 求最长链变成了最长链计数,其余没有变化. 这一次考试为了保险起见本蒟蒻还是写了上次没写的辅助数组. 代码: #include<bits/stdc++.h> #define ...
-
2018.09.08 NOIP模拟eat(贪心)
签到水题啊... 这题完全跟图论没有关系. 显然如果确定了哪些点会被选之后顺序已经不重要了.于是我们给点按权值排序贪心从大向小选. 我们要求的显然就是∑i(a[i]−(n−i))" role ...
-
2018.10.24 bzoj2064: 分裂(状压dp)
传送门 状压dp好题. 考虑对于两个给出的集合. 如果没有两个元素和相等的子集,那么只能全部拼起来之后再拆开,一共需要n1+n2−2n1+n2-2n1+n2−2. 如果有呢? 那么对于没有的就是子问题 ...
-
2018.10.08 NOIP模拟 栅栏(树状数组+rand)
传送门 今天的送分题. 首先考虑每次给要围上栅栏的矩阵里的整体加上1,如果栅栏被撤销就整体减1,最后比较两个点的值是否相同来进行判断. 然而这样的效果并不理想,很容易卡掉. 进一步思考,我们第iii次 ...
-
2018.11.08 NOIP模拟 班车(倍增+dfs+bit)
传送门 对于每个点离线处理出向上走2i2^i2i班车到的最上面的点. 然后每个询问(u,v)(u,v)(u,v)先把(u,v)(u,v)(u,v)倍增到刚好走不到lcalcalca的情况(有一个点如果 ...
-
2018.11.08 NOIP模拟 水管(简单构造)
传送门 仔细读题会发现只要所有点点权之和等于0一定有解. 如何构造? 直接当做树来构造就行了,非树边都赋值成0就行. 代码
-
2018.11.08 NOIP模拟 景点(倍增+矩阵快速幂优化dp)
传送门 首先按照题意构造出转移矩阵. 然后可以矩阵快速幂求出答案. 但是直接做是O(n3qlogm)O(n^3qlogm)O(n3qlogm)的会TTT掉. 观察要求的东西发现我们只关系一行的答案. ...
-
2018.10.08 NOIP模拟 序列(主席树)
传送门 T2防ak题? 其实也不是很难(考试时sb了). 直接变形一下求出区间长度在[l2,r2][l2,r2][l2,r2]之间,中位数≤l1−1\le l1-1≤l1−1的区间数,和区间长度在[l ...
随机推荐
-
javascript多态 - 类形式实现demo
/* *多态 * 对传入的参数做判断以实现多种调用方式 */ //类形式实现 function Add(){ function zero(){ return 10; } function one(nu ...
-
为什么我的联想打印机M7450F换完墨粉之后打印机显示请更换墨粉盒?这是我的墨盒第一次灌粉&#183;、
需要打印机清零,可以网上查到的,要不就去买颗芯片换上关掉机器 →开机的同时按住功能按扭不松手开机→进入维修模式→翻到84功能项→按OK→用下翻键找到PROCESS CHECK→按OK 按扭→关机→正常 ...
-
jar文件签名
1.生成密钥: keytool -genkey -keystore key.keystore -alias key -validity 3650 将在当前目录下生成一个key.keystore文件, ...
-
Kylin上chromium不能用flash的解决命令
sudo apt-get update sudo apt-get install pepperflashplugin-nonfree sudo update-pepperflashplugin-non ...
-
[译] 开发者角度,王道之论:Android 与 Windows Phone
前几天,在codeproject搜索Silverlight资料,偶然看到这篇文章,耐心读了2遍,非常不错:文章通过访谈聊天形式叙述,2位主角目前在<斯法克斯国家工程学院>软件学院上学. 周 ...
-
JS+CSS简单实现DIV遮罩层显示隐藏【转藏】
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...
-
cli/php.ini和fpm/php.ini的区别
1. 当从命令行执行PHP binary时,cli/php.ini会被使用,你可以通过在命令行运行php --ini来查看. 2. 当PHP运行做为FPM时,会使用fpm/phh.ini,其中一种情况 ...
-
mysql查看表大小
mysql查看表大小 一:命令 show table status like 'table_name'\G; mysql> show table status like 'x'\G; . row ...
-
oracle查看用户属于哪个表空间
select username,default_tablespace from dba_users where username='用户名';
-
Cannot find module &#39;webpack/lib/node/NodeTemplatePlugin&#39; 问题原因和解决方案
当我配置了html-webpack-plugin 打包时报了这个错,查看了一下package.json发现没有webpack,说明使用了全局安装的webapck,导致的版本差异. 这里在本地安装web ...