oj.uz

Submission #49325

# Submission time Handle Problem Language Result Execution time Memory
49325 2018-05-26T01:35:08 Z ami Sažetak (COCI17_sazetak) C++14
32 / 160
 494 ms 664 KB 
#include <bits/stdc++.h>
#define sz(c)      int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using i64 = long long;

i64 rev(i64 a, i64 m) {
  return a==1 ? 1 : (1 - rev(m%a,a) * m) / a + m;
}

i64 gcd(i64 a, i64 b) {
  return a==0?b:gcd(b%a,a);
}

i64 lcm(i64 a,i64 b) {
  return a/gcd(a,b) * b;
}

i64 crt2(i64 a1, i64 m1, i64 a2, i64 m2) {
  if (a1>a2) {
    swap(a1,a2);
    swap(m1,m2);
  }
  i64 g=gcd(m1,m2);
  if (a1%g != a2%g) return -1;
  i64 k=(a2-a1)/g * rev(m1/g,m2/g) % (m2/g);
  return a1 + k*m1;
}

i64 lcm(vector<pair<int,int>> rems) {
  i64 res=rems[0].first;
  rep(i,1,sz(rems)) res=lcm(res,rems[i].first);
  return res;
}

i64 crt(int n,vector<pair<int,int>> rems) {
  i64 m,x;
  tie(m,x)=rems[0];
  rep(i,1,sz(rems)) {
    x=crt2(x,m,rems[i].second,rems[i].first);
    m=lcm(m,rems[i].first);
    if (x==-1 || x>n) return 0;
  }
  return x;
}

int n,m;
int a[11];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout<<fixed<<setprecision(10);

  cin>>n>>m;
  rep(i,0,m) cin>>a[i];
  a[m++]=n;

  i64 res=0;
  rep(mask,0,1<<m) {
    if (__builtin_popcount(mask)<2) continue;

    i64 total=0;
    for (int submask=mask-1; submask>0; submask=(submask-1)&mask) {
      vector<pair<int,int>> rems;
      rep(i,0,m) if (mask>>i&1) rems.emplace_back(a[i],submask>>i&1);
      i64 s=lcm(rems);
      i64 t=crt(n,rems);
      if (t!=0) {
        total+=n/s;
        if (n%s>=t) total+=1;
      }
    }

    if (__builtin_popcount(mask)%2==0) res+=total; else res-=total;
  }
  cout<<res<<endl;
}

Subtask #1
32.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Incorrect 18 ms 436 KB Output isn't correct
4 Incorrect 2 ms 640 KB Output isn't correct
5 Incorrect 4 ms 664 KB Output isn't correct
6 Incorrect 7 ms 664 KB Output isn't correct
7 Incorrect 14 ms 664 KB Output isn't correct
8 Incorrect 24 ms 664 KB Output isn't correct
9 Incorrect 195 ms 664 KB Output isn't correct
10 Incorrect 494 ms 664 KB Output isn't correct