【NOIP2016提高A组五校联考2】running
2024-10-07 05:39:56
题目
小胡同学是个热爱运动的好孩子。
每天晚上,小胡都会去操场上跑步,学校的操场可以看成一个由n个格子排成的一个环形,格子按照顺时针顺序从0 到n- 1 标号。
小胡观察到有m 个同学在跑步,最开始每个同学都在起点(即0 号格子),每个同学都有个步长ai,每跑一步,每个同学都会往顺时针方向前进ai 个格子。由于跑道是环形的,如果一个同学站在n-1 这个格子上,如果他前进一个格子,他就会来到0。
他们就这样在跑道上上不知疲倦地跑呀跑呀。小胡同学惊奇地发现,似乎有些格子永远不会被同学跑到,他想知道这些永远不会被任何一个同学跑到的格子的数目,你能帮帮他
吗?(我们假定所有同学都跑到过0 号格子)。
分析
首先对于一个人 i, 显然,那么它所能到达的格子一定是$gcd(ai,n) \(的倍数。
所以我们枚举n的约数d,如果有一个i,\)gcd(a_i,n)|d\(,说明所有\)gcd(j,n) = d$ 的格子都能被到达,答案加上 \(φ(\dfrac{n}{d})\) 即可。
#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=2147483647;
const int mo=1000000007;
const int N=55;
using namespace std;
int a[N],n,m,ans;
int gcd(int x,int y)
{
if(y==0) return x;
if(x<y) return gcd(y,x);
else return gcd(y, x%y);
}
int phi(int x)
{
int sum=x,e=x;
for(int i=2;i<=int(sqrt(e));i++)
{
if(x%i==0)
{
sum=sum/i*(i-1);
while(x%i==0) x/=i;
}
}
if(x>1)
{
sum=sum/x*(x-1);
}
return sum;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d",&a[i]);
for(int i=1;i<=int(sqrt(n));i++)
{
if(n%i==0)
{
for(int j=1;j<=m;j++)
if(i%gcd(a[j],n)==0)
{
ans+=phi(n/i);
break;
}
for(int j=1;j<=m;j++)
if((n/i)%gcd(a[j],n)==0)
{
ans+=phi(i);
break;
}
}
}
cout<<n-ans<<endl;
}
最新文章
- Appium移动自动化框架
- 4中map遍历的方法
- CSS3魔法堂:CSS3滤镜及Canvas、SVG和IE滤镜替代方案详解[转]
- c# 后台调前台的js
- Workspace in use or cannot be created, choose a different one.--错误解决办法
- Shell变量命名规则
- android 定时器总结
- [Swift]LeetCode560. 和为K的子数组 | Subarray Sum Equals K
- python数据包之利器scapy用法!
- OS + Linux RedHat 6.3 QA
- Mysql5.7实现主从复制、基于GTID的主从复制、并行复制
- fasterxml.jackson 将对象转换为json报错处理
- ubuntu 创建swap分区
- [LintCode] Longest Increasing Continuous subsequence
- Selenium 爬取全国水质周报Word
- R语言学习 第四篇:函数和流程控制
- Netty Pipeline、channel、Context之间的数据流向
- arm家族小检阅
- NET 读取Word文档信息
- bzoj千题计划134:bzoj3124: [Sdoi2013]直径
热门文章
- 【ABAP系列】SAP 一个完整的SAP的Abap例子(idoc,edi文件的相互转换)
- Python学习之表的数据类型
- 意想不到的JavaScript(每日一题2)
- USACO3.3 A Game【区间dp】
- USACO1.6 回文质数 Prime Palindromes
- javascript number与isNan
- 【7.9校内test】T2 极值问题
- 洛谷P1029 最大公约数和最小公倍数问题 (简单数学题)
- Ubuntu下更新Pycharm时权限不够(PyCharm does not have write access to...)
- source与./执行的区别