Submission #49328

#	Time	Username	Problem	Language	Result	Execution time	Memory
49328		ami	Sažetak (COCI17_sazetak)	C++14	48 / 160	28 ms	704 KiB

sazetak

#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==-1 || x>n) 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];

  i64 res=0;
  rep(mask,0,1<<m) {
    i64 p=1;
    bool skip=false;
    rep(i,0,m) if (mask>>i&1) {
      p=lcm(p,a[i]);
      if (p>n) {
        skip=true;
        break;
      }
    }
    if (skip) 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;
  }
  rep(i,0,m) if (n%a[i]==1) ++res;
  cout<<res<<endl;
}

• Subtask 1: 48 / 160