oj.uz

Submission #49327

# Submission time Handle Problem Language Result Execution time Memory
49327 2018-05-26T02:20:14 Z ami Sažetak (COCI17_sazetak) C++14
160 / 160
 177 ms 748 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;
}

pair<i64,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<0 || x>n || m<0) return {0,0};
  }
  return {x,m};
}

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)&mask; 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,t;
      tie(s,t)=crt(n,rems);
      if (s!=0) {
        total+=n/t;
        if (s<=n%t) total+=1;
      }
    }

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

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 10 ms 484 KB Output is correct
4 Correct 14 ms 580 KB Output is correct
5 Correct 3 ms 644 KB Output is correct
6 Correct 6 ms 644 KB Output is correct
7 Correct 9 ms 644 KB Output is correct
8 Correct 16 ms 644 KB Output is correct
9 Correct 173 ms 748 KB Output is correct
10 Correct 177 ms 748 KB Output is correct