首页    技术博客    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(容斥)
推荐阅读
  • bit

    嵌入式系统实验：GPIO控制与按键响应

    本报告记录了嵌入式软件设计课程中的第二次实验，主要探讨了使用KEIL V5开发环境和ST固件库进行GPIO控制及按键响应编程的方法。通过实际操作，加深了对嵌入式系统硬件接口编程的理解。 ... [详细]
  • php

    深入解析Unity3D游戏开发中的音频播放技术

    深入解析Unity3D游戏开发中的音频播放技术
    在游戏开发中，音频播放是提升玩家沉浸感的关键因素之一。本文将探讨如何在Unity3D中高效地管理和播放不同类型的游戏音频，包括背景音乐和效果音效，并介绍实现这些功能的具体步骤。 ... [详细]
  • php

    JavaScript 中引号的多层嵌套使用技巧

    JavaScript 中引号的多层嵌套使用技巧
    本文详细介绍了在 JavaScript 编程中如何处理引号的多级嵌套问题，包括双引号、单引号以及转义字符的正确使用方法。 ... [详细]
  • php

    深入理解Awk文本处理工具

    Awk是一款功能强大的文本分析与处理工具，尤其在数据解析和报告生成方面表现突出。它通过读取由换行符分隔的记录，并按照指定的字段分隔符来划分和处理这些记录，从而实现复杂的数据操作。 ... [详细]
  • php

    JavaScript 页面卸载事件详解 (onunload)

    JavaScript 页面卸载事件详解 (onunload)
    当用户从页面离开时（如关闭页面或刷新页面），会触发 onunload 事件，此时可以执行预设的脚本。需要注意的是，不同的浏览器对 onunload 事件的支持程度可能有所不同。 ... [详细]
  • php

    为何Compose与Swarm之后仍有Kubernetes的诞生？

    为何Compose与Swarm之后仍有Kubernetes的诞生？
    探讨在已有Compose和Swarm的情况下，Kubernetes是如何以其独特的设计理念和技术优势脱颖而出，成为容器编排领域的领航者。 ... [详细]
  • php

    AOJ1024 清洁机器人2.0

    本文介绍了一个来自AIZU ONLINE JUDGE平台的问题，即清洁机器人2.0。该问题来源于某次编程竞赛，涉及复杂的算法逻辑与实现技巧。 ... [详细]
  • php

    egg实现登录鉴权（七）：权限管理

    egg实现登录鉴权（七）：权限管理
    权限管理包含三部分：访问页面的权限，操作功能的权限和获取数据权限。页面权限：登录用户所属角色的可访问页面的权限功能权限：登录用户所属角色的可访问页面的操作权限数据权限：登录用户所属 ... [详细]
  • php

    iOS开发中的UIView及其子类应用

    本文介绍了用户界面（User Interface, UI）的基本概念，以及在iOS应用程序中UIView及其子类的重要性和使用方式。文章详细探讨了UIView如何作为用户交互的核心组件，以及它与其他UI控件和业务逻辑的关系。 ... [详细]
  • php

    线性表中的元素删除算法

    本文探讨了线性表中元素的删除方法，包括顺序表和链表的不同实现策略，以及这些策略在实际应用中的性能分析。 ... [详细]
  • client

    深入解析Apache Mina开发指南

    本文由chszs撰写，详细介绍了Apache Mina框架的核心开发流程及自定义协议处理方法。文章涵盖从创建IoService实例到协议编解码的具体步骤，适合希望深入了解Mina框架应用的开发者。 ... [详细]
  • php

    P3796 AC自动机强化版题解 - Aho-Corasick Algorithm

    本文提供了一个关于AC自动机（Aho-Corasick Algorithm）的详细解析与实现方法，特别针对P3796题目进行了深入探讨。文章不仅涵盖了AC自动机的基本概念，还重点讲解了如何通过构建失败指针（fail pointer）来提高字符串匹配效率。 ... [详细]
  • php

    LeetCode 102 - 二叉树层次遍历详解

    LeetCode 102 - 二叉树层次遍历详解
    本文详细解析了LeetCode第102题——二叉树的层次遍历问题，提供了C++语言的实现代码，并对算法的核心思想和具体步骤进行了深入讲解。 ... [详细]
  • php

    解决UIScrollView自动偏移问题的方法

    解决UIScrollView自动偏移问题的方法
    本文介绍了一种有效的方法来解决在使用UIScrollView时出现的自动向下偏移的问题，通过调整特定的属性设置，可以确保滚动视图正常显示。 ... [详细]
  • php

    Python3爬虫入门：pyspider的基本使用[python爬虫入门]

    Python3爬虫入门：pyspider的基本使用[python爬虫入门]
    Python学习网有大量免费的Python入门教程，欢迎大家来学习。本文主要通过爬取去哪儿网的旅游攻略来给大家介绍pyspid ... [详细]
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社区 版权所有