hdu5514 非2的次幂容斥原理
2024-10-19 07:26:44
/*
1
126 223092870
210 330 390 462 510 546 570 690 714 770 798 858 910 966 1122 1155 1190 1254 1326 1330 1365 1430 1482 1518 1610 1785 1794 1870 1938 1995 2002 2090 2145 2210 2346 2415 2470 2530 2618 2622 2805 2926 2990 3003 3094 3135 3230 3315 3458 3542 3705 3795 3910 3927 4186 4370 4389 4485 4522 4641 4845 4862 5005 5187 5313 5434 5474 5865 6118 6279 6545 6555 6578 6783 7106 7293 7315 7735 8151 8211 8398 8602 8645 8855 9177 9614 9867 10166 10465 10659 11305 11362 12155 12597 12903 13585 13685 14421 14858 15249 15295 16445 17017 17043 17765 19019 20995 21505 22287 23023 24035 24871 25415 28405 29393 30107 33649 35581 37145 39767 46189 52003 55913 62491 81719 96577
*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <cctype>
#define N 10000
#define LL long long
#define U unsigned
using namespace std;
int cas=,T;
int n,m,a[N+],d[N+],dn,v[N+],c[N+];
int gcd(int a,int b)
{
return b==?a:gcd(b,a%b);
}
void fac()
{
dn=;
int x=sqrt(m)+0.5;
for(int i=;i<=x;i++)
{
if(m%i==)
{
d[dn++]=i;
d[dn++]=m/i;
}
}
sort(d,d+dn);
}
int main()
{
//freopen("1.in","w",stdout);
//freopen("1.in","r",stdin);
//freopen("out1","w",stdout);
scanf("%d",&T);
while(T--)
{
memset(v,,sizeof(v));//要走的次数
memset(c,,sizeof(c));//已经走的次数
scanf("%d%d",&n,&m);
set<int>g;
for(int i=;i<n;i++) { scanf("%d",a+i);g.insert(gcd(m,a[i]%m)); }
fac();
for(set<int>::iterator it=g.begin();it!=g.end();it++) //初始化,*it的倍数约数都要走一次
{
for(int j=;j<dn;j++) if(d[j]% *it==) v[j]=;
}
LL ans=;
//for(int i=0;i<dn;i++) printf("%d ",d[i]);printf("\n");
for(int i=;i<dn;i++)
{
if(v[i])
{
int dif=v[i]-c[i]; //d[i]本来要走的次数-已经走了的次数=现在要走的次数
ans+=(LL)m*(m/d[i]-)/*dif;
for(int j=i+;j<dn;j++) if(d[j]%d[i]==) c[j]+=dif;//d[i]走过之后d[i]的倍数也已经走了dif次,所以c[j]+=dif
}
}
printf("Case #%d: %lld\n",cas++,ans);
}
//printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
return ;
}
最新文章
- WPF 自定义模板 Button闪亮效果
- css疑难汇总
- svn服务配置和日常维护命令
- 浏览器何时发送一个Option请求
- Cheatsheet: 2013 07.21 ~ 07.31
- prettyprint
- Java学习笔记——Java工厂模式之简单工厂
- Javascript中NaN、null和undefinded的区别
- 【续】抓个Firefox的小辫子,jQuery表示不背这黑锅,Chrome,Edge,IE8-11继续围观中
- linux 查看CPU、内存、磁盘信息命令
- GoldenGate HANDLECOLLISIONS参数使用说明
- [原创]Delphi XE10 dxLayoutControl 控件应用指南
- ElasicSearch(1)
- YAML基本语法
- delphi如何在form显示出来后处理指定的事件(例如自动登录)
- [PHP] 链表数据结构(单链表)
- java的静态内部类
- springboot redis 缓存跨域丢失问题
- PAT B1005 继续(3n+1)猜想 (25 分)
- JS中getElementByID,getElementsByName,getElementsByTagName的区别