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

    新浪笔试题

    1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • js

    深入理解Cookie与Session会话管理

    深入理解Cookie与Session会话管理
    本文详细介绍了如何通过HTTP响应和请求处理浏览器的Cookie信息，以及如何创建、设置和管理Cookie。同时探讨了会话跟踪技术中的Session机制，解释其原理及应用场景。 ... [详细]
  • js

    QUIC协议：快速UDP互联网连接

    QUIC协议：快速UDP互联网连接
    QUIC（Quick UDP Internet Connections）是谷歌开发的一种旨在提高网络性能和安全性的传输层协议。它基于UDP，并结合了TLS级别的安全性，提供了更高效、更可靠的互联网通信方式。 ... [详细]
  • js

    2023 ARM嵌入式系统全国技术巡讲

    2023 ARM嵌入式系统全国技术巡讲旨在分享ARM公司在半导体知识产权(IP)领域的最新进展。作为全球领先的IP提供商，ARM在嵌入式处理器市场占据主导地位，其产品广泛应用于90%以上的嵌入式设备中。此次巡讲将邀请来自ARM、飞思卡尔以及华清远见教育集团的行业专家，共同探讨当前嵌入式系统的前沿技术和应用。 ... [详细]
  • go

    优化ListView性能

    优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • js

    深入理解 Oracle 存储函数：计算员工年收入

    深入理解 Oracle 存储函数：计算员工年收入
    本文介绍如何使用 Oracle 存储函数查询特定员工的年收入。我们将详细解释存储函数的创建过程，并提供完整的代码示例。 ... [详细]
  • js

    国内BI工具迎战国际巨头Tableau，稳步崛起

    国内BI工具迎战国际巨头Tableau，稳步崛起
    尽管商业智能（BI）工具在中国的普及程度尚不及国际市场，但近年来，随着本土企业的持续创新和市场推广，国内主流BI工具正逐渐崭露头角。面对国际品牌如Tableau的强大竞争，国内BI工具通过不断优化产品和技术，赢得了越来越多用户的认可。 ... [详细]
  • js

    深入探讨JSP技术的优缺点

    本文详细分析了JSP（JavaServer Pages）技术的主要优点和缺点，帮助开发者更好地理解其适用场景及潜在挑战。JSP作为一种服务器端技术，广泛应用于Web开发中。 ... [详细]
  • js

    2018回顾与2019展望

    本文总结了2018年的关键成就，包括职业变动、购车、考取驾照等重要事件，并分享了读书、工作、家庭和朋友方面的感悟。同时，展望2019年，制定了健康、软实力提升和技术学习的具体目标。 ... [详细]
  • settings

    Python配置文件读写指南

    本文详细介绍如何使用Python进行配置文件的读写操作，涵盖常见的配置文件格式（如INI、JSON、TOML和YAML），并提供具体的代码示例。 ... [详细]
  • js

    四载相伴，与51CTO学院共成长

    在计算机技术的学习道路上，51CTO学院以其专业性和专注度给我留下了深刻印象。从2012年接触计算机到2014年开始系统学习网络技术和安全领域，51CTO学院始终是我信赖的学习平台。 ... [详细]
  • js

    CSS 布局：液态三栏混合宽度布局

    CSS 布局：液态三栏混合宽度布局
    本文介绍了如何使用 CSS 实现液态的三栏布局，其中各栏具有不同的宽度设置。通过调整容器和内容区域的属性，可以实现灵活且响应式的网页设计。 ... [详细]
  • js

    Linux 系统启动故障排除指南：MBR 和 GRUB 问题

    Linux 系统启动故障排除指南：MBR 和 GRUB 问题
    本文详细介绍了 Linux 系统启动过程中常见的 MBR 扇区和 GRUB 引导程序故障及其解决方案，涵盖从备份、模拟故障到恢复的具体步骤。 ... [详细]
  • js

    通过类型和标签选择元素

    本文介绍了如何使用jQuery根据元素的类型（如复选框）和标签名（如段落）来获取DOM对象。这有助于更高效地操作网页中的特定元素。 ... [详细]
  • js

    Xcode 中多行代码缩进技巧

    本文介绍如何在 Xcode 中使用快捷键和菜单命令对多行代码进行缩进，包括右缩进和左缩进的具体操作方法。 ... [详细]
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社区 版权所有