BZOJ 5302: [Haoi2018]奇怪的背包-白红宇

强烈建议你试试无所不能的chatGPT，快点击我

BZOJ 5302: [Haoi2018]奇怪的背包

阅读量：7051 次

发布时间：2019-06-28

本文共 763 字，大约阅读时间需要 2 分钟。

首先根据裴蜀定理，v[i]等价于gcd(v[i],P)，w[i]等价于gcd(w[i],P)，所以我们只要求出P的约数的答案，F[i][j]表示用了前i种约数，能产生最小值为第j种约数的方案数，统计答案即可

#include
     
      #include
      
       #include
       using namespace std;const int mod=1e9+7;int n,q,P,top,vec[1000005],ans[1000005],Sum[1000005],V[1000005],F[2005][2005];map
        
          M;int gcd(int a,int b){	if (b==0) return a;	return gcd(b,a%b);}int main(){	scanf("%d%d%d",&n,&q,&P);	for (int i=1; i*i<=P; i++)		if (P%i==0){			vec[++top]=i;			M[i]=top;			if (i*i!=P) {				vec[++top]=P/i;				M[P/i]=top;			}		}	for (int i=1; i<=top; i++) Sum[i]=1;	for (int i=1; i<=n; i++) {		scanf("%d",&V[i]);		V[i]=gcd(V[i],P);		(Sum[M[V[i]]]<<=1)%=mod; 	}	F[0][M[P]]=1;	for (int i=0; i

　　

转载于:https://www.cnblogs.com/silenty/p/9788397.html

你可能感兴趣的文章

在kubernets中搭建jenkins服务

iEclipse-不只是Eclipse的开发者社区

Oracle个人的一些记录

20.分屏查看命令 less命令

感谢付费客户不覺流年似水(271558528) 对C#ASP.NET通用权限管理组件的改进意见，已修正...

MySQL5.6.17学习笔记（四）复合分区及分区管理

android 让 TextView 自带滚动条

PHP过滤常见html标签的正则表达式

注册与登录界面的美化

win2003远程桌面不自动注销，自动锁定时间

7个顶级心理寓言

我的友情链接

2.vi 和 vim 编辑器

java异常设计

服务器的几种时间同步

我的友情链接

WPF“动画序列”框架的初步研究与实现（附源码）

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！

当前时间: 2025-02-07 08:38:54 当前IP: 18.119.127.230 联系邮箱:javaeecc@qq.com Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2

强烈建议你试试无所不能的CHAT-GPT，快点击我

强烈建议你试试无所不能的CHAT-GPT，快点击我