题目

小胡同学是个热爱运动的好孩子。

每天晚上,小胡都会去操场上跑步,学校的操场可以看成一个由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;
}

最新文章

  1. Appium移动自动化框架
  2. 4中map遍历的方法
  3. CSS3魔法堂:CSS3滤镜及Canvas、SVG和IE滤镜替代方案详解[转]
  4. c# 后台调前台的js
  5. Workspace in use or cannot be created, choose a different one.--错误解决办法
  6. Shell变量命名规则
  7. android 定时器总结
  8. [Swift]LeetCode560. 和为K的子数组 | Subarray Sum Equals K
  9. python数据包之利器scapy用法!
  10. OS + Linux RedHat 6.3 QA
  11. Mysql5.7实现主从复制、基于GTID的主从复制、并行复制
  12. fasterxml.jackson 将对象转换为json报错处理
  13. ubuntu 创建swap分区
  14. [LintCode] Longest Increasing Continuous subsequence
  15. Selenium 爬取全国水质周报Word
  16. R语言学习 第四篇:函数和流程控制
  17. Netty Pipeline、channel、Context之间的数据流向
  18. arm家族小检阅
  19. NET 读取Word文档信息
  20. bzoj千题计划134:bzoj3124: [Sdoi2013]直径

热门文章

  1. 【ABAP系列】SAP 一个完整的SAP的Abap例子(idoc,edi文件的相互转换)
  2. Python学习之表的数据类型
  3. 意想不到的JavaScript(每日一题2)
  4. USACO3.3 A Game【区间dp】
  5. USACO1.6 回文质数 Prime Palindromes
  6. javascript number与isNan
  7. 【7.9校内test】T2 极值问题
  8. 洛谷P1029 最大公约数和最小公倍数问题 (简单数学题)
  9. Ubuntu下更新Pycharm时权限不够(PyCharm does not have write access to...)
  10. source与./执行的区别