首页    技术博客    PHP教程    数据库技术    前端开发   HTML5    Nginx    php论坛
新用户注册 | 会员登录
加入会员，解锁专属内容
取消
热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

hdu5514Frogs(容斥)

作者：采蘑菇的灵的fans | 来源：互联网 | 2023-10-12 17:40
FrogsTimeLimit:20001000MS(JavaOthers)MemoryLimit:6553665536K(JavaOthers)TotalSubmission(s)
Frogs

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1315    Accepted Submission(s): 443


Problem Description
There are m stones lying on a circle, and n frogs are jumping over them.
The stones are numbered from 0 to m−1 and the frogs are numbered from 1 to n. The i-th frog can jump over exactly ai stones in a single step, which means from stone j mod m to stone (j+ai) mod m (since all stones lie on a circle).

All frogs start their jump at stone 0, then each of them can jump as many steps as he wants. A frog will occupy a stone when he reach it, and he will keep jumping to occupy as much stones as possible. A stone is still considered ``occupied" after a frog jumped away.
They would like to know which stones can be occupied by at least one of them. Since there may be too many stones, the frogs only want to know the sum of those stones‘ identifiers.
 
Input
There are multiple test cases (no more than 20), and the first line contains an integer t,
meaning the total number of test cases.

For each test case, the first line contains two positive integer n and m - the number of frogs and stones respectively (1≤n≤104, 1≤m≤109).

The second line contains n integers a1,a2,?,an, where ai denotes step length of the i-th frog (1≤ai≤109).
 
Output
For each test case, you should print first the identifier of the test case and then the sum of all occupied stones‘ identifiers.
 
Sample Input
3
2 12
9 10
3 60
22 33 66
9 96
81 40 48 32 64 16 96 42 72
 
Sample Output
Case #1: 42
Case #2: 1170
Case #3: 1872
/*
hdu 5514 Frogs(容斥)

problem:
有n只青蛙和围成一个圈的m个石头. 每只青蛙可以跳a[i]步. 求所有被占领过的石头的编号和

solve:
可以发现青蛙会经过 GCD(a[i],m)的倍数的点.但是有很多重复跳过的石头. 所以会想到容斥.
如果暴力肯定要GG.   可以发现青蛙只会经过gcd(x,m)的点,也就是m的因子.
所以可以把枚举m改成枚举m的因子.  然后利用容斥减去重复的就行.  

hhh-2016-08-30 16:30:55
*/
#pragma comment(linker,"/STACK:124000000,124000000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define lson  i<<1
#define rson  i<<1|1
#define ll long long
#define clr(a,b) memset(a,b,sizeof(a))
#define scanfi(a) scanf("%d",&a)
#define scanfs(a) scanf("%s",a)
#define scanfl(a) scanf("%I64d",&a)
#define key_val ch[ch[root][1]][0]
#define inf 1e9
using namespace std;
const ll mod = 1e9+7;
const int maxn = 20005;
int fac[maxn];
int fcnt;
int vis[maxn],hac[maxn];

int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a;
}

int main()
{
    int T,n,m;
//    freopen("in.txt","r",stdin);
    scanfi(T);
    int cas = 1;
    while(T--)
    {
        scanfi(n),scanfi(m);
        fcnt = 0;
        for(int i = 1;i*i <= m;i++)
        {
            if(m % i == 0)
            {
                fac[fcnt++] = i;
                if(i *i != m)
                    fac[fcnt ++ ] = m/i;
            }
        }
        sort(fac,fac+fcnt);
//        for(int i = 0;i

hdu 5514 Frogs(容斥)
推荐阅读
  • int

    HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法

    HDU 2372 El Dorado（DP）的最长上升子序列长度求解方法
    本文介绍了解决HDU 2372 El Dorado问题的一种动态规划方法，通过循环k的方式求解最长上升子序列的长度。具体实现过程包括初始化dp数组、读取数列、计算最长上升子序列长度等步骤。 ... [详细]
  • java

    求解hdu 1003 java题目的动态规划优化方法

    本文讨论了如何优化解决hdu 1003 java题目的动态规划方法，通过分析加法规则和最大和的性质，提出了一种优化的思路。具体方法是，当从1加到n为负时，即sum(1,n)sum(n,s)，可以继续加法计算。同时，还考虑了两种特殊情况：都是负数的情况和有0的情况。最后，通过使用Scanner类来获取输入数据。 ... [详细]
  • java

    OC学习笔记之@property和@synthesize

    本文介绍了OC学习笔记中的@property和@synthesize，包括属性的定义和合成的使用方法。通过示例代码详细讲解了@property和@synthesize的作用和用法。 ... [详细]
  • java

    VB.NET在线急等问题解决方法，如何统计数据库字段下的数据并显示在文本框里？

    本文介绍了一个在线急等问题解决方法，即如何统计数据库中某个字段下的所有数据，并将结果显示在文本框里。作者提到了自己是一个菜鸟，希望能够得到帮助。作者使用的是ACCESS数据库，并且给出了一个例子，希望得到的结果是560。作者还提到自己已经尝试了使用"select sum(字段2) from 表名"的语句，得到的结果是650，但不知道如何得到560。希望能够得到解决方案。 ... [详细]
  • java

    JS进修笔记——闭包的运转机制和作用域

    本文介绍了闭包的定义和运转机制，重点解释了闭包如何能够接触外部函数的作用域中的变量。通过词法作用域的查找规则，闭包可以访问外部函数的作用域。同时还提到了闭包的作用和影响。 ... [详细]
  • int

    lua语言闭包、模式匹配、日期、编译、模块的特性及应用

    本文介绍了lua语言中闭包的特性及其在模式匹配、日期处理、编译和模块化等方面的应用。lua中的闭包是严格遵循词法定界的第一类值，函数可以作为变量自由传递，也可以作为参数传递给其他函数。这些特性使得lua语言具有极大的灵活性，为程序开发带来了便利。 ... [详细]
  • int

    Android 新闻App的本地服务器搭建教程

    本文介绍了在开发Android新闻App时，搭建本地服务器的步骤。通过使用XAMPP软件，可以一键式搭建起开发环境，包括Apache、MySQL、PHP、PERL。在本地服务器上新建数据库和表，并设置相应的属性。最后，给出了创建new表的SQL语句。这个教程适合初学者参考。 ... [详细]
  • java

    Java实现大数乘法（分治算法）

    本文介绍了使用Java实现大数乘法的分治算法，包括输入数据的处理、普通大数乘法的结果和Karatsuba大数乘法的结果。通过改变long类型可以适应不同范围的大数乘法计算。 ... [详细]
  • java

    Java工具类库Hutool介绍及功能概述

    本文介绍了Java工具类库Hutool，该工具包封装了对文件、流、加密解密、转码、正则、线程、XML等JDK方法的封装，并提供了各种Util工具类。同时，还介绍了Hutool的组件，包括动态代理、布隆过滤、缓存、定时任务等功能。该工具包可以简化Java代码，提高开发效率。 ... [详细]
  • java

    如何使用Java获取服务器硬件信息和磁盘负载率

    如何使用Java获取服务器硬件信息和磁盘负载率
    本文介绍了使用Java编程语言获取服务器硬件信息和磁盘负载率的方法。首先在远程服务器上搭建一个支持服务端语言的HTTP服务，并获取服务器的磁盘信息，并将结果输出。然后在本地使用JS编写一个AJAX脚本，远程请求服务端的程序，得到结果并展示给用户。其中还介绍了如何提取硬盘序列号的方法。 ... [详细]
  • java

    SpringBoot yml 配置 多配置文件,开发环境,生产环境配置文件分开

    原文地址:https:www.cnblogs.combaoyipSpringBoot_YML.html1.在springboot中，有两种配置文件，一种 ... [详细]
  • int

    C#之数据集：DataSet对象的使用及相关方法详解

    本文介绍了C#中数据集DataSet对象的使用及相关方法详解，包括DataSet对象的概述、与数据关系对象的互联、Rows集合和Columns集合的组成，以及DataSet对象常用的方法之一——Merge方法的使用。通过本文的阅读，读者可以了解到DataSet对象在C#中的重要性和使用方法。 ... [详细]
  • java

    Hibernate基础映射

    在说Hibernate映射前，我们先来了解下对象关系映射ORM。ORM的实现思想就是将关系数据库中表的数据映射成对象，以对象的形式展现。这样开发人员就可以把对数据库的操作转化为对 ... [详细]
  • java

    Spring特性实现接口多类的动态调用详解

    Spring特性实现接口多类的动态调用详解
    本文详细介绍了如何使用Spring特性实现接口多类的动态调用。通过对Spring IoC容器的基础类BeanFactory和ApplicationContext的介绍，以及getBeansOfType方法的应用，解决了在实际工作中遇到的接口及多个实现类的问题。同时，文章还提到了SPI使用的不便之处，并介绍了借助ApplicationContext实现需求的方法。阅读本文，你将了解到Spring特性的实现原理和实际应用方式。 ... [详细]
  • java

    [大整数乘法] java代码实现

    [大整数乘法] java代码实现
    本文介绍了使用java代码实现大整数乘法的过程，同时也涉及到大整数加法和大整数减法的计算方法。通过分治算法来提高计算效率，并对算法的时间复杂度进行了研究。详细代码实现请参考文章链接。 ... [详细]
author-avatar
采蘑菇的灵的fans
这个家伙很懒，什么也没留下！
Tags | 热门标签
RankList | 热门文章
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有