fork download
copy 
  1. //package com.company;
  2.  
  3.  
  4. import java.io.*;
  5. import java.util.*;
  6. class Main implements Runnable {
  7.     int size[];
  8.     static int e9 = 1000000007;
  9.     int max = Integer.MIN_VALUE;
  10.     long max1 = Long.MIN_VALUE;
  11.     long min1 = Long.MAX_VALUE;
  12.     long fib[][];
  13.     static class FastReader {
  14.         BufferedReader br;
  15.         StringTokenizer st;
  16.  
  17.         public FastReader() {
  18.             br = new BufferedReader(new
  19.                     InputStreamReader(System.in));
  20.         }
  21.  
  22.         String next() {
  23.             while (st == null || !st.hasMoreElements()) {
  24.                 try {
  25.                     st = new StringTokenizer(br.readLine());
  26.                 } catch (IOException e) {
  27.                     e.printStackTrace();
  28.                 }
  29.             }
  30.             return st.nextToken();
  31.         }
  32.  
  33.         int nextInt() {
  34.             return Integer.parseInt(next());
  35.         }
  36.  
  37.         long nextLong() {
  38.             return Long.parseLong(next());
  39.         }
  40.  
  41.         double nextDouble() {
  42.             return Double.parseDouble(next());
  43.         }
  44.  
  45.         String nextLine() {
  46.             String str = "";
  47.             try {
  48.                 str = br.readLine();
  49.             } catch (IOException e) {
  50.                 e.printStackTrace();
  51.             }
  52.             return str;
  53.         }
  54.     }
  55.     int parent[];
  56.     int rank[];
  57.     ArrayList<ArrayList<Integer>> arrayLists;
  58.     ArrayList<Integer> arr[];
  59.     long fib1[][];
  60.     long r[];
  61.     int n;
  62.     int m;
  63.     long co=0;
  64.     long size1[];
  65.     long v[];
  66.     public static void main(String[] args) throws IOException {
  67.         new Thread(null,new Main(),"Main",1<<28).start();
  68.     }
  69.  
  70.     public void run(){
  71. //        FastReader scanner = new FastReader();
  72.             Scanner scanner = new Scanner(System.in);
  73. //            BufferedReader bufferedReader=new BufferedReader(new InputStreamReader(System.in));
  74. //            String s;
  75.         PrintWriter printWriter = new PrintWriter(System.out);
  76. //        System.out.println(1<<6);
  77.     //    long t=scanner.nextLong();
  78.  
  79.  
  80.  
  81. //Solution Starts
  82.  
  83.  
  84.         high:while (scanner.hasNext()) {
  85.             long n=scanner.nextLong();
  86.             int m=scanner.nextInt();
  87.             long arr[]=new long[m];
  88.             long ans=0;
  89.             long ans1=1;
  90.             for (int i = 0; i < m; i++) {
  91.                 long a=scanner.nextLong();
  92.                 arr[i]=a;
  93.                 ans1=ans1*a;
  94.             }
  95.             for (int i = 0; i < m; i++) {
  96.                 ans=gcd(ans,arr[i]);
  97.             }
  98.             long lcm=ans1/ans;
  99. //            System.out.println(lcm);
  100.             long or=0;
  101.             for (int i = 1; i <=lcm ; i++) {
  102.                 boolean w=true;
  103.                 for (int j = 0; j < m; j++) {
  104.                     if(i%arr[j]==0){
  105.                         w=false;
  106.                         break;
  107.                     }
  108.                 }
  109.                 if(w){
  110.                     or++;
  111.                 }
  112.             }
  113.             long u=n/lcm;
  114.             or=or*u;
  115.             long y=u*lcm;
  116.             for (long i = y+1; i <n; i++) {
  117.                 boolean w=true;
  118.                 for (int j = 0; j < m; j++) {
  119.                     if(i%arr[j]==0){
  120.                         w=false;
  121.                         break;
  122.                     }
  123.                 }
  124.                 if(w){
  125.                     or++;
  126.                 }
  127.             }
  128.             printWriter.println(or);
  129.         }
  130.         printWriter.flush();
  131.     }
  132.  
  133. //Solution Ends
  134.  
  135.  
  136.  
  137.  
  138.     static long mod=1_000_000_007;
  139.     public long mul(long a, long b) {
  140. //        System.out.println(a+" "+b);
  141.         return ((a)%mod*(b)%mod);
  142.     }
  143.     public long fact(int x) {
  144.         long ans=1;
  145.         for (int i=2; i<=x; i++) ans=mul(ans, i);
  146.         return ans;
  147.     }
  148.     public long fastPow(long base, long exp) {
  149.         if (exp==0) return 1;
  150.         long half=fastPow(base, exp/2);
  151.         if (exp%2==0) return mul(half, half);
  152.         return mul(half, mul(half, base));
  153.     }
  154.     public long modInv(long x) {
  155.         return fastPow(x, mod-2);
  156.     }
  157.     public long nCk(int n, int k) {
  158.         return mul(fact(n), mul(modInv(fact(k)), modInv(fact(n-k))));
  159.     }
  160.     public void parent(int n){
  161.         parent=new int[n+1];
  162.         size=new int[n+1];
  163.         rank=new int[n+1];
  164.         for (int i = 0; i <=n; i++) {
  165.             parent[i]=i;
  166.             rank[i]=0;
  167. //            size[i]=1;
  168.         }
  169.     }
  170.     public void union(int i,int j){
  171.         int root1=find(i);
  172.         int root2=find(j);
  173. //            if(root1 != root2) {
  174. //                parent[root2] = root1;
  175. ////                sz[a] += sz[b];
  176. //            }
  177.         if(root1==root2){
  178.             return;
  179.         }
  180.         if(rank[root1]>rank[root2]){
  181.             parent[root2]=root1;
  182.             size[root1]+=size[root2];
  183.         }
  184.         else if(rank[root1]<rank[root2]){
  185.             parent[root1]=root2;
  186.             size[root2]+=size[root1];
  187.         }
  188.         else{
  189.             parent[root2]=root1;
  190.             rank[root1]+=1;
  191.             size[root1]+=size[root2];
  192.         }
  193.     }
  194.     public int find(int p){
  195.         if(parent[p]!=p){
  196.             if(parent[p]==-1){
  197.                 return parent[p];
  198.             }
  199.             parent[p]=find(parent[p]);
  200.         }
  201.         return parent[p];
  202.     }
  203.     public double dist(double x1,double y1,double x2,double y2){
  204.         double e=(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
  205.         double e1=Math.sqrt(e);
  206.         return e1;
  207.     }
  208.     public void make(int p){
  209.         parent[p]=p;
  210.         rank[p]=1;
  211.     }
  212.     Random rand = new Random();
  213.     public void sort(int[] a, int n) {
  214.         for (int i = 0; i < n; i++) {
  215.             int j = rand.nextInt(i + 1);
  216.             int tmp = a[i];
  217.             a[i] = a[j];
  218.             a[j] = tmp;
  219.         }
  220.         Arrays.sort(a, 0, n);
  221.     }
  222.     public long gcd(long a,long b){
  223.         if(b==0){
  224.             return a;
  225.         }
  226.         return gcd(b,a%b);
  227.     }
  228.     //    public void dfs(ArrayList<Integer> arrayList){
  229. //        for (int i = 0; i < arrayList.size(); i++) {
  230. //            if(v1[arrayList.get(i)]==false){
  231. //                v1[arrayList.get(i)]=true;
  232. //                dfs(arrayLists.get(i));
  233. //            }
  234. //        }
  235. //    }
  236.     public double fact(double h){
  237.         double sum=1;
  238.         while(h>=1){
  239.             sum=(sum%e9)*(h%e9);
  240.             h--;
  241.         }
  242.         return sum%e9;
  243.     }
  244.     public long primef(double r){
  245.         long c=0;
  246.         long ans=1;
  247.         while(r%2==0){
  248.             c++;
  249.             r=r/2;
  250.         }
  251.         if(c>0){
  252.             ans*=2;
  253.         }
  254.         c=0;
  255. //            System.out.println(ans+" "+r);
  256.         for (int i = 3; i <=Math.sqrt(r) ;i+=2) {
  257.             while(r%i==0){
  258. //                    System.out.println(i);
  259.                 c++;
  260.                 r=r/i;
  261.             }
  262.             if(c>0){
  263.                 ans*=i;
  264.             }
  265.             c=0;
  266.         }
  267.         if(r>2){
  268.             ans*=r;
  269.         }
  270.         return ans;
  271.     }
  272.     public long divisor(double r,long n,long k){
  273.         long c=0;
  274. //        if(n==3)
  275. //            System.out.println(r+" "+n+" "+k+" "+"l");
  276.         for (int i =2; i <=Math.sqrt(r)&&i<k&&i<n; i++) {
  277.             if(r%i==0){
  278.                 if(r/i==i){
  279.                     c++;
  280.                 }
  281.                 else{
  282.                     if(r/i<n){
  283.                         c+=2;
  284.                     }else{
  285.                         c++;
  286.                     }
  287.                 }
  288.             }
  289.         }
  290.         return c;
  291.     }
  292. }
  293. class Pair {
  294.     int x;
  295.     int y;
  296.     int z;
  297.     public Pair(int x,int y) {
  298.         this.x = x;
  299.         this.y = y;
  300. //        this.z=z;
  301.     }
  302.  
  303.     // @Override
  304. //    public int hashCode() {
  305. //        int hash = 37;
  306. //        return this.x * hash + this.y;
  307. //    }
  308. //
  309. //    @Override
  310. //    public boolean equals(Object o1) {
  311. //        if (o1 == null || o1.getClass() != this.getClass()) {
  312. //            return false;
  313. //        }
  314. //        Pair o = (Pair) o1;
  315. //        if (o.x == this.x && o.y == this.y) {
  316. //            return true;
  317. //        }
  318. //        return false;
  319. //    }
  320. }
  321. class Sorting implements Comparator<Pair> {
  322.     public int compare(Pair p1, Pair p2) {
  323. //        if(p1.y==p2.y){
  324. //            return Long.compare(p1.x,p2.x);
  325. //        }else {
  326.         return Long.compare(p1.x, p2.x);
  327.         // }
  328.     }
  329. }
  330. class Edge{
  331.     int s=0;
  332.     int d=0;
  333.     int c=0;
  334.     public Edge(int s,int d,int c){
  335.         this.s=s;
  336.         this.d=d;
  337.         this.c=c;
  338.     }
  339. }
Success #stdin #stdout 0.11s 51512KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/v2Q2t9
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!