akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include<algorithm>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){
    int N,M;
    while(cin >> N >> M && N+M!=0){

        vector<int> h(N+1,0);
        REP(i,N){
            cin >> h[i];
        }
        vector<int> w(M+1,0);
        REP(i,M){
            cin >> w[i];
        }
        //入力終わり

        vector<int> H(1000*N,0);
        vector<int> W(1000*M,0);


        int hs=0;
        REP(p,N){
            hs+=h[p];
            int ha=hs;
            H[ha]++;
            REP(i,N-p-1){
                ha+=h[i+p+1];
                ha-=h[i];
                H[ha]++;
            }
        }
        //H[i番目からp+i-1番目までのhの和<=1500000]でカウント

        int ws=0;
        REP(p,M){
            ws+=w[p];
            int wa=ws;
            W[wa]++;
            REP(i,M-p-1){
                wa+=w[i+p+1];
                wa-=w[i];
                W[wa]++;
            }
        }
        //W[]も同様

        int count=0;
        int mini=min(hs,ws);
        FOR(i,1,mini+1){
            count+=H[i]*W[i];
        }
        //H[t]*W[t]が長さtの正方形の数

        cout << count << endl;
    }
    return 0;
}


Measured memory_bytes: 14656
#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
 
vector<ll> fact(10,1); 
ll gcd(ll n1,ll n2){
    ll maxm=max(n1,n2);
    ll minm=min(n1,n2);
    if((maxm%minm)==0) return minm;
    else return gcd(minm,maxm%minm);
}
 
ll power(ll x, ll y) 
{ 
	ll temp; 
    if( y == 0) 
        return 1; 
    temp = power(x, y/2)%mod; 
    if (y%2 == 0) 
        return temp*temp%mod; 
    else
        return (x*temp%mod)*temp%mod; 
}
ll ifact(long long k){
    return power(fact[k],mod-2)%mod;
}
ll ncr(ll n, ll r){
    if(n<r) return 0;
    ll num=1;
    ll den=1;
    ll g;
    rep(i,1,r+1){
        num=num*(n-i+1);
        den=den*(i);
        g=gcd(num,den);
        num=num/g;
        den=den/g;
    }
    return num;
}
int main(){
   ios;
   int t=1;//cin>>t;
   while(t--){
	  ll n,x;
      cin>>n;
      unordered_map<ll,ll> m;
      rep(i,0,n){
          cin>>x;
          m[x]++;
      }
      ll ans=0;
      for(auto it=m.begin();it!=m.end();++it){
          if(it->second>=it->first) ans+=it->second-it->first;
          else ans+=it->second;
      }
      cout<<ans;
    } 
}

Measured memory_bytes: 7316
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long; 
using pii =  pair<int, int>;
using pll =  pair<long long, long long>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
//constexpr long long MOD = 998244353LL;
template<class T, class U> inline bool chmax(T &a, U b) { if (a < b) { a = b; return true;} return false; }
template<class T, class U> inline bool chmin(T &a, U b) { if (a > b) { a = b; return true;} return false; }
////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int N; cin >> N;
    vector<int> A(N);
    rep(i,N) cin >> A[i];
    bitset<4000400> dp;
    dp[0] = 1;
    rep(i,N) {
        dp |= dp<<A[i];
    }
    dp[0] = 0;
    int M = dp.count();
    M = (M+1)/2;
    rep(i,4000400) {
        if (dp.test(i)) M--;
        if (!M) {
            cout << i << ln;
            return 0;
        }
    }
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;

int main() {
  string N; cin >> N;
  int a = 0;
  for (int i = 0; i < N.length(); i++) {
    a += N[i]-'0';
  }
  if (stoi(N) % a == 0) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <queue>

using namespace std;

typedef long long ll;

ll n, ans;
string s;
ll ls[5500][5500];

int main() {
  cin >> n >> s;
  
  for (int i = 0; i < n; i++) {
    ls[i][i] = n - i;
    ll j = 1, len = 0;
    while (i+j < n) {
      while (i+j+len < n and s[i+len] == s[i+j+len]) len++;
      ls[i][i+j] = len;
      ans = max(ans, min(j, len));
      if (len == 0) {
        j++;
        continue;
      }
      ll k = 1;
      while (i+j+k < n and i+k + ls[i][i+k] < i+len) {
        ls[i][i+j+k] = ls[i][i+k];
        ans = max(ans, min(j, ls[i][i+k]));
        k++;
      }
      j += k;
      len -= k;
    }
  }     
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 215296
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
const ll INF = 1LL << 60;
const ll MOD = (ll) 1e9 + 7;

int main(){
    ll n, m;
    cin >> n >> m;
    if (n > m) swap(n, m);
    if (n == 1) {
        if (m == 1) {
            cout << 1 << "\n";
            return 0;
        }
        cout << m - 2 << "\n";
        return 0;
    }
    cout << n * m - (n - 1) * 2 - (m - 1) * 2 << "\n";
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define read freopen("in.in","r",stdin)
#define write freopen("out.out","w",stdout)
#define FastIO ios::sync_with_stdio(0)
typedef long long ll;
int n,k; 
int cost[100005];
int memo[100005];
int dp(int idx) {
	if (idx > n)return 9999999;
	if (idx == n-1)return 0;

	int &ret = memo[idx];
	if (ret != -1)return ret;

	ret = 1e9;
	for (int i = 1; i <=k; i++)
		if(idx+i < n)
		ret = min(ret, dp(idx + i) + abs(cost[idx] - cost[idx + i]));
	return ret;
}
int main() {
	FastIO;
#ifndef ONLINE_JUDGE
	//write; read;
#endif 
	memset(memo, -1, sizeof memo);
	cin >> n >> k;
	for (int i = 0; i < n; i++)
		cin >> cost[i];
	cout << dp(0) << endl;
	
		
	return 0;
}

Measured memory_bytes: 5760
N = int(input())
T = list(map(int,input().split()))
M = int(input())
P = []
X = []
for i in range(M):
    p, x = map(int,input().split())
    P.append(p)
    X.append(x)
T_total = 0

for i in range(N):
    T_total += T[i]

for i in range(M):
    p = P[i] - 1
    ans = T_total - T[p] + X[i]
    print(ans)

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
  int n, m;
  cin >> n >> m;
  char arr[n][m];
  int dp[n][m];

  for (int i = 0; i < n; ++i)
  {
    for (int j = 0; j < m; ++j)
    {
      cin >> arr[i][j];
    }
  }

  dp[n-1][m-1] = 1;

  //return 0;

  for (int i = n-1; i >= 0; --i)
  {
    for (int j = m-1; j >= 0; --j)
    {
       if(i == n-1 && j == m-1) continue;
       
       if(arr[i][j] == '#') 
        {dp[i][j] = 0; continue; }
       dp[i][j] = 0;
       if(i+1 < n)
       {
        dp[i][j] += dp[i+1][j];
        dp[i][j] %= mod;
      }
       if(j + 1 < m)
       {
        dp[i][j] += dp[i][j + 1];
        dp[i][j] %= mod;
       } 



       dp[i][j] %= mod;

    }
  }

  cout << dp[0][0];
  return 0;
}

Measured memory_bytes: 5120
N, M = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(M)]
box = sorted(box, key= lambda x: x[1])
rmax = box[0][1]
ans = 1
for i in range(1, M):
    if box[i][0] >= rmax:
        rmax = box[i][1]
        ans += 1
    else:
        continue
print(ans)

Measured memory_bytes: 29852
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,k;
  cin >> n >> k;
  string s;
  cin >> s;
  if (s[k-1]=='A'){
    s[k-1] = 'a';
  }
  if (s[k-1]=='B'){
    s[k-1] = 'b';
  }
  if (s[k-1]=='C'){
    s[k-1] = 'c';
  }
  cout << s << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base :: sync_with_stdio(false);
    int n; cin >> n;
        
    vector<int> dp(n + 1, 0);
    int maxx = 0;

    for(int i = 0; i < n; ++i) {
        int x; cin >> x;
        if(x - 1 >= 0) {
            dp[x] = dp[x - 1] + 1;
        } else {
            dp[x] = 1;
        }
        maxx = max(dp[x], maxx);
    }

    cout << n - maxx << "\n";
}

Measured memory_bytes: 1024
#if 1
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
#include <array>
#include <deque>
#include <algorithm>
#include <utility>
#include <cstdint>
#include <functional>
#include <iomanip>
#include <numeric>
#include <assert.h>
#include <bitset>
#include <list>

auto& in = std::cin;
auto& out = std::cout;
#define all_range(C) std::begin(C), std::end(C)
const double PI = 3.141592653589793238462643383279502884197169399375105820974944;

int32_t N,C;

int32_t cost[50][50];
std::vector<int32_t> V[3];
std::vector<std::pair<int32_t, int32_t>> topC[3];

int main()
{
	using std::endl;
	in.sync_with_stdio(false);
	out.sync_with_stdio(false);
	in.tie(nullptr);
	out.tie(nullptr);

	in >> N >> C;
	for (size_t i = 0; i < C; i++)
		for (size_t j = 0; j < C; j++)
	{
		in >> cost[i][j];
	}
	for (size_t i = 0; i < N; i++)
		for (size_t j = 0; j < N; j++)
	{
		int v;
		in >> v; --v;
		V[(i + j) % 3].push_back(v);
	}

	for (size_t i = 0; i < 3; i++)
	{
		for (int32_t c = 0; c < C; c++)
		{
			int32_t costsum = 0;
			for (auto& from : V[i]) {
				costsum += cost[from][c];
			}
			topC[i].emplace_back(costsum, c);
		}

		std::sort(all_range(topC[i]));
	}

	int32_t mincost = 500000000;
	bool used[50] = {};
	for (size_t i = 0; i < 3; i++)
	{
		used[topC[0][i].second]= true;
		for (size_t j = 0; j < 3; j++)
		{
			if (used[topC[1][j].second])continue;
			used[topC[1][j].second] = true;
			for (size_t k = 0; k < 3; k++)
			{
				if (used[topC[2][k].second])continue;
				used[topC[2][k].second] = true;

				mincost = std::min(mincost, topC[0][i].first + topC[1][j].first + topC[2][k].first);

				used[topC[2][k].second] = false;
			}
			used[topC[1][j].second] = false;
		}
		used[topC[0][i].second] = false;
	}
	out << mincost << endl;

	return 0;
}
#endif


Measured memory_bytes: 2152
/* ex3_3
   moka223711 */

#include <stdio.h>

int main(void){
	int num, K, i = 1;
	scanf("%d %d", &num, &K);

	// numがK^i以上のとき、K進法はi桁で表せる
	// numをKで割り続けて何回割れるかをiでカウントする
	while(num >= K){
		num /= K;
		i++;
	}

	printf("%d", i);

	return 0;
}


Measured memory_bytes: 128
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		Set<String> set = new HashSet<>();
		for (int i = 0; i < n; i++) {
			set.add(sc.next());
		}
		sc.close();

		System.out.println(set.size());
	}
}


Measured memory_bytes: 76832
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	char b; cin >> b;

	if(b == 'A') cout << 'T' << endl;
	else if(b == 'T') cout << 'A' << endl;
	else if(b == 'C') cout << 'G' << endl;
	else cout << 'C' << endl;

	return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<functional>
#include<utility>
#include<stack>
#include<queue>
#include<cmath>
#include<list>
#include<cstdint>
#include<vector>
#include<map>
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,rept)	for(ll i = 0; i<rept;i++)
typedef long long ll;

ll nCr(ll n, ll r) {
	if (r > n) { return 0; }
	if (r * 2 > n) r = n - r;
	ll dividend = 1;
	ll divisor = 1;
	for (ll i = 1; i <= r; ++i) {
		dividend *= (n - i + 1);
		divisor *= i;
	}
	return dividend / divisor;
}
ll sumdigit(ll n) {
	ll dig = 0, sum = 0;
	while (n) {
		dig = n % 10;
		sum = sum + dig;
		n = n / 10;
	}
	return sum;
}



int main() {
	int a, b;
	std::cin >> a >> b;
	if (a == 1) {
		a =99;
	}
	if (b == 1) {
		b = 99;
	}
	if (a > b) {
		std::cout << "Alice" << std::endl;
	}
	else if (a == b) {
		std::cout << "Draw" << std::endl;
	}
	else {
		std::cout << "Bob" << std::endl;
	}
}

Measured memory_bytes: 256
// includes
#include <bits/stdc++.h>
using namespace std;

// macros
#define pb emplace_back
#define mk make_pair
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr)
#define whole(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define bit(n) (1LL<<(n))
#define F first
#define S second
// functions
template <typename T> void unique(T& c){c.erase(std::unique(c.begin(), c.end()), c.end());}
template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;}
template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;}
template <typename T> ostream &operator<<(ostream &os, const vector<T>& vec){for(int i = 0; i < vec.size(); i++){ os << vec[i]; if(i + 1 != vec.size())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << "(" << p.first << ", " << p.second << ")"; return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << "(" << itr->first << ", " << itr->second << ")"; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const unordered_map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << "(" << itr->first << ", " << itr->second << ")"; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
//  types
using ll = long long int;
using P = pair<int, int>;
// constants
const int inf = 1e9;
const ll linf = 1LL << 60;
const double EPS = 1e-10;
const int mod = 1000000007;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};
// io
struct fast_io{
  fast_io(){ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(20);}
} fast_io_;


int main(int argc, char const* argv[])
{
  string t; cin >> t;
  rep(i, sz(t)){
    if(t[i] == '?'){
      t[i] = 'D';
    }
  }
  cout << t << endl;
  return 0;
}


Measured memory_bytes: 3772
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vc = vector<char>;
using vvl = vector<vl>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;

int main(){
  ll x, a, b;
  cin >> x >> a >> b;

  if(abs(x - a) < abs(x - b))
    cout << 'A' << endl;
  else
    cout << 'B' << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define r(i,n) for(int i = 0; i<n; i++)
typedef long long ll;
using namespace std;

int main(){
  ll n,count=0;
  string s;
  cin >> n;
  map<string,ll> m;
  r(i,n){
    cin >> s;
    sort(s.begin(),s.end());
    m[s]++;
  }
  for(auto it=m.begin(); it!=m.end();it++){
    if((*it).second>1){
      count+=(*it).second*((*it).second-1)/2;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 11136
#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, L; cin >> N >> L;
    vector<int> taste(N);
    if (L >= 0) {
        cout << (N + 2 * L - 1) * N / 2 - L << endl;
    }
    else if (N >= 1 - L) {
        cout << (N + 2 * L - 1) * N / 2 << endl;
    }
    else {
        cout << (N + 2 * L - 1) * N / 2 - (L + N - 1) << endl;
    }
    }

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main(){
    int N;
    cin >> N;
    vector<pair<int, int>> edges;
    for(int i=1; i<=N; i++){
        int ng;
        if(N%2){
            ng = N-i;
        }else{
            ng = N+1-i;
        }
        for(int j=1; j<i; j++) if(j != ng) edges.emplace_back(i, j);
    }
    cout << edges.size() << endl;
    for(auto& p : edges) cout << p.first << " " << p.second << endl;
}


Measured memory_bytes: 384
N,M=map(int,input().split())
H=list(map(int,input().split()))
max_=[True]*N
for i in range(M):
    a,b=map(lambda x:int(x)-1,input().split())
    if(H[a]>=H[b]):
        max_[b]=False
    if(H[a]<=H[b]):
        max_[a]=False
ans=0
for i in range(N):
    if max_[i]:
        ans+=1
print(ans)

Measured memory_bytes: 20124
def main():
    N = int(input())
    D, X = map(int, input().split())

    A = [0] * N
    for i in range(N):
        A[i] = int(input())

    cnt = X
    for a in A:
        cnt += 1 + (D - 1) // a

    print(cnt)


main()

Measured memory_bytes: 38484
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807
ll ans = 0;

int main()
{
string s;
cin >> s;
ll k;
cin >> k;
set<string> v;

int len=(int)(s.length());
char first='z';
rep(i,len){
  if(s[i]<first)first=s[i];
}
rep(i,len){
  if(s[i]==first){
    rep1(j,k+1){
      v.insert(s.substr(i, j));
    }
  }
}
char second='z';
rep(i,len){
  if(s[i]<second&&s[i]!=first)second=s[i];
}
rep(i,len){
  if(s[i]==second){
    rep1(j,k+1){
      v.insert(s.substr(i, j));
    }
  }
}
char third='z';
rep(i,len){
  if(s[i]<third&&s[i]!=first&&s[i]!=second)third=s[i];
}
rep(i,len){
  if(s[i]==third){
    rep1(j,k+1){
      v.insert(s.substr(i, j));
    }
  }
}
auto itr=v.begin();
rep(i,k-1){
  
  itr++;
}
cout << *itr << endl;
return 0;
}

Measured memory_bytes: 384
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>

#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,n) for(int i=n;i>=a;--i)
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define mod 1000000007
#define show(n) cerr<<#n<<" = "<<n<<endl
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl

//ここからAtCoder向けdefine
#define yes cout << "YES" << endl
#define no cout << "NO" << endl

using namespace std;

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using pint = pair<int,int>;

const int INF = (1 << 30);

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    vi vec(3);
    rep(i,3){
        cin>>vec[i];
    }
    sort(all(vec));


    ll diff=vec[2]-vec[1];
    vec[0]+=diff%2;
    ll ans=(diff+1)/2;
    //show(ans);
    diff=vec[2]-vec[0];
    ans+=(diff+1)/2;
    //show(ans);
    ans+=diff%2;
    cout<<ans<<endl;
    //shows(vec);
    return 0;
}

Measured memory_bytes: 256
N = int(input())
ans = 0
if N < 105:
    print(ans)
    exit()
for i in range(105,N+1,2):
    cnt = 0
    for j in range(1,i+1):
        if i%j == 0:
            cnt += 1
    if cnt == 8:
        ans += 1
print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<math.h>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<stdlib.h>
using namespace std;
#define PI 3.14159265358979
typedef  long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#include<set>


//---------------------------------------------
 

int main(void)
{
    float r;
    cin>>r;

    cout<<2*r*PI<<endl;

}

Measured memory_bytes: 3776
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define ANS(n) cout << (n) << endl

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FORR(i,a,b) for(int i=(a);i>=(b);i--)

#define ALL(obj) (obj).begin(),(obj).end()

#define pii pair<int,int>

#define pb(a) push_back(a)
#define mp make_pair

int main()
{
	int n,k;
	cin >> n >> k;
	char d[k];
	FOR(i,0,k)cin >> d[i];
	while(1){
		string n_string = to_string(n);
		//cout << n_string << "\n";
		bool able = true;
		FOR(i,0,(int)n_string.size()){
			FOR(j,0,k){
				//cout << n_string[i] << " " << d[j] << "\n";
				if(n_string[i] == d[j]){
					able = false;
					break;
				}
			}
		}
		if(able)break;
		n++;
	}
	ANS(n);
	return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();

		int ans = 0;
		for (int i = 1; i <= n; i++) {
			int c = 0;
			int d = i;
			
			while (d > 0) {
				c += d % 10;
				d /= 10;
			}
			
			if (a <=  c && c <= b) {
				ans += i;
			}
		}
		System.out.println(ans);
	}
}

Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
const int INFTY = (1<<30);

long long cnt = 0;

void merge(vector<int> &A, int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;
  vector<int> L(n1+1);
  vector<int> R(n2+1);
  for (int i = 0; i < n1; i++) {
    L[i] = A[left+i];
  }
  for (int j = 0; j < n2; j++) {
    R[j] = A[mid+j];
  }
  L[n1] = INFTY;
  R[n2] = INFTY;
  int i = 0;
  int j = 0;
  for (int k = left; k < right; k++) {
    if (L[i] <= R[j]) {
      A[k] = L[i];
      i++;
    }
    else {
      A[k] = R[j];
      j++;
      cnt += (n1 - i);
    }
  }
}

int mergeSort(vector<int> &A, int left, int right) {
  if (right - left > 1) {
    int mid = (left + right) / 2;
    mergeSort(A, left, mid);
    mergeSort(A, mid, right);
    merge(A, left, mid, right); 
  }
}

int main() {
  int n;
  cin >> n;
  vector<int> A(n);
  for (int i = 0; i < n; i++) {
    cin >> A[i];
  }
  mergeSort(A, 0, n);
  cout << cnt << endl;
}


Measured memory_bytes: 4396
import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;
import java.util.Map;
class Main{
  public static void main(String[] args){
   Scanner sc = new Scanner(System.in);
   int n = sc.nextInt();
   HashMap<String,Integer> ars = new HashMap<>();
   long a = 0L;
   for(int i = 0; i < n; i++){
     char[] input = sc.next().toCharArray();
     Arrays.sort(input);
     String str = String.valueOf(input);
     int cnt=0;
     if(ars.containsKey(str)){
       cnt = ars.get(str);
       a += cnt;
     } 
     ars.put(str,cnt+1);
   }
   System.out.println(a);
  }
}

Measured memory_bytes: 55984
#include <stdio.h>

int main(void)          
{
	int a, b, c;
	scanf("%d %d %d", &a, &b, &c);

	if (a < b && b < c) 
	{
		printf("Yes\n");

	}
	else
	{
		printf("No\n");
	}


	return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<n;i++)
#define inf 1e9+7
using namespace std;
typedef long long ll;
const double pi=acos(-1);

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
    int n;
    cin >> n;
    vector<int> A(n);
    for(int i=0;i<n;i++) cin >> A[i];
    int ans=A[0];
    for(int i=1;i<n;i++) ans=gcd(ans,A[i]);
    cout << ans << endl;
}

Measured memory_bytes: 3764
#include <algorithm>
#include <bitset>
#include <cassert>
#include <climits>
#include <cmath>
#include <ctime>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <memory.h>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long double LD;
typedef long long LL;
typedef pair<LL, LL> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#ifdef LOCAL
#define DEBUG(x) { cerr << "# " << #x << ": " << x << endl;}
#else
#define DEBUG(x)
#endif
mt19937_64 mt(time(0));
/*---------------------------------------------------------------------------------------------------
　　　　　　　　　　　 ∧＿∧
　　　　　 ∧＿∧ 　（´<_｀ ）　 Welcome to My Coding Space!
　　　　 （ ´_ゝ`）　/　 ⌒i
　　　　／　　　＼　 　  |　|
　　　 /　　 /￣￣￣￣/　　|
　 ＿_(__ﾆつ/　    ＿/ .| .|＿＿＿＿
　 　　　＼/＿＿＿＿/　（u　⊃
---------------------------------------------------------------------------------------------------*/






int main() {
  ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  cout.precision(10); cout << fixed;
#ifdef LOCAL
  freopen("../test.txt", "r", stdin);
    // freopen("../output.txt", "w", stdout);
#endif
  int n; cin >> n;
  int cur = 0, i = 0;
  vector<bool> used(n, false);
  while (true) {
    i++;
    cur = (cur * 10 + 7) % n;
    if (cur == 0) break;
    if (used[cur]) {
      i = -1;
      break;
    }
    used[cur] = true;
  }
  cout << i << '\n';






/*---------------------------------------Coding Space End------------------------------------------*/
#ifdef LOCAL
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s." << endl;
#endif
  return 0;
}
/* author:  txingml */
/* picture is from hamayanhamayan(CF handle) */


Measured memory_bytes: 3288
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>

int main() {

    int n, X, A, tmp1, tmp2, i = 0, ans = 0, cst = 1;

    std::cin >> n;

    int p[n];

    while(std::cin >> tmp1){
        p[i] = tmp1;
        i++;
        if(i >= n){
            break;
        }
    }

    for(int i=1; i<n-1; i++){
        if((p[i-1]< p[i] && p[i] < p[i+1])
            || (p[i+1]< p[i] && p[i] < p[i-1])){
            ans++;
        }
    }

    std::cout << ans << std::endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define rep(i, n) for(int i = 0; i < n; i++)
#define REP(i, a, b) for(int i = a; i < b; i++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define fi first
#define se second
#define debug(x) cerr <<__LINE__<< ": " <<#x<< " = " << x << endl
#define debug_vec(v) cerr<<__LINE__<<": "<<#v<<" = ";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF = (1<<30) - 1;
const ll LINF = (1LL<<60) - 1;

void solve() {
    ll n, k;
    cin >> n >> k;
    vector<ll> A(n);
    rep(i, n) cin >> A[i];
    sort(all(A));
    ll l = -LINF, r = LINF;
    while(r - l > 1) {
        ll mid = (r + l) / 2;
        ll cnt = 0;
        for (ll a : A) {
            if (a == 0) {
                if (mid >= 0) cnt += n;
            } else if (a < 0) {
                ll v;
                if (mid >= 0) v = mid / a;
                else {
                    if (mid % a == 0) v = mid / a;
                    else v = mid / a + 1;
                }
                cnt += A.end() - lower_bound(all(A), v);
            } else {
                ll v;
                if (mid >= 0) v = mid / a;
                else {
                    if (mid % a == 0) v = mid / a;
                    else v = mid / a - 1;
                }
                cnt += upper_bound(all(A), v) - A.begin();
            }
            if (a * a <= mid) cnt--;
        }
        cnt /= 2;
        if (cnt >= k) r = mid;
        else l = mid;
    }
    cout << r << endl;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    solve();
    return 0;
}


Measured memory_bytes: 4768
#include <bits/stdc++.h>
using namespace std;

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> v;
  if (n == 3) {
    cout << "2\n1 3\n2 3" << endl;
    return 0;
  }
  if (n == 4) {
    cout << "4\n1 2\n1 3\n4 2\n4 3" << endl;
    return 0;
  }
  if (n % 2) {
    v.push_back({n});
    for (int i = 1; i <= n / 2; ++i) {
      v.push_back({i, n - i});
    }
  } else {
    for (int i = 1; i <= n / 2; ++i) {
      v.push_back({i, n - i + 1});
    }
  }
  v.push_back(v[0]);
  vector<pair<int, int>> ans;
  for (int i = 0; i < v.size() - 1; ++i) {
    for (int j : v[i]) {
      for (int k : v[i + 1]) {
        ans.emplace_back(j, k);
      }
    }
  }
  cout << ans.size() << endl;
  for (auto a : ans) {
    cout << a.first << ' ' << a.second << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>

using namespace std;

int n, a[100010];

int partition(int p, int r) {
    int x = a[r], i = p - 1;
    for (int j = p; j < r; j++) {
        if (a[j] > x) continue;
        i++;
        swap(a[i], a[j]);
    }
    swap(a[i + 1], a[r]);
    return i + 1;
}

int main(void) {
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int v = partition(0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i) cout << " ";
        if (i == v) cout << "[" << a[i] << "]";
        else cout << a[i];
    }
    cout << endl;

    return 0;
}


Measured memory_bytes: 3460
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
	if (a%b == 0) return b;
	if (b%a==0) return a;
	if(b<a)
		swap (a,b);
	return gcd(b%a,a);
}


int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n;i++)
		cin >> a[i];
	int res = gcd(a[0],a[1]);
	for (int i = 0; i < n;i++)
		res = gcd(res,a[i]);
	cout << res;
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
using namespace std;
const int N = 100010;
int dp[N][3];
int main(){
    fast;
	int n, i, a, b, c;
	cin >> n;
	memset(dp, 0, sizeof dp);
	for (i = 0; i < n; i++) {
		cin >> a >> b >> c;
		dp[i + 1][0] = a + max(dp[i][1], dp[i][2]);
		dp[i + 1][1] = b + max(dp[i][0], dp[i][2]);
		dp[i + 1][2] = c + max(dp[i][0], dp[i][1]);
	}
	cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << "\n";
	return 0;
}


Measured memory_bytes: 4788
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Edge = pair<int, int>;
using Graph = vector<vector<Edge>>;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
const ll MOD = 1000000007;
const ll nmax = 8;
const ll INF = 1e9;
bool graph[nmax][nmax];
vector<vector<ll>> dist = vector<vector<ll>>(nmax, vector<ll>(nmax, INF));
void warshall_floyd(ll n)
{
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            for (size_t k = 0; k < n; k++)
            {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }
}

class UnionFind
{
public:
    vector<ll> Parent;

    UnionFind(ll N)
    {
        Parent = vector<ll>(N, -1);
    }
    ll find(ll A)
    {
        if (Parent[A] < 0)
            return A;
        return Parent[A] = find(Parent[A]);
    }

    ll size(ll A)
    {
        return -Parent[find(A)];
    }

    bool Union(ll A, ll B)
    {
        A = find(A);
        B = find(B);
        if (A == B)
        {
            return false;
        }
        if (size(A) < size(B))
            swap(A, B);

        Parent[A] += Parent[B];
        Parent[B] = A;

        return true;
    }
};

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    ll g = gcd(a, b);
    return a / g * b;
}

ll mulMod(ll a, ll b)
{
    return (((a % MOD) * (b % MOD)) % MOD);
}

ll powMod(ll a, ll p)
{
    if (p == 0)
    {
        return 1;
    }
    else if (p % 2 == 0)
    {
        ll half = powMod(a, p / 2);
        return mulMod(half, half);
    }
    else
    {
        return mulMod(powMod(a, p - 1), a);
    }
}

ll ceil(ll a, ll b)
{
    return (a + b - 1) / b;
}

ll dp[100010];
void solve(long long N, std::vector<long long> h)
{
    for (int i = 0; i <= N ; i++)
    {
        dp[i] = INF;
    }
    dp[1] = 0;
    for (int i = 1; i <= N; i++)
    {
        dp[i + 1] = min(dp[i] + abs(h[i - 1] - h[i]), dp[i + 1]);
        dp[i + 2] = min(dp[i] + abs(h[i - 1] - h[i + 1]), dp[i + 2]);
    }

    cout << dp[N] << endl;
}

int main()
{
    long long N;
    scanf("%lld", &N);
    std::vector<long long> h(N);
    for (int i = 0; i < N; i++)
    {
        scanf("%lld", &h[i]);
    }
    solve(N, std::move(h));
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>

using namespace std;

int main() {
    long long h, n, tr, sum = 0;
    cin >> h >> n;
    for (int i = 0; i < n; ++i) {
        cin >> tr;
        sum += tr;
    }
    if (sum >= h)
        cout << "Yes\n";
    else
        cout << "No\n";
}

Measured memory_bytes: 256
#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#define lc (x<<1)
#define rc (x<<1|1)
#define gc getchar()//(p1==p2&&(p2=(p1=buf)+fread(buf,1,size,stdin),p1==p2)?EOF:*p1++)
#define mk make_pair
#define pi pair<int,int>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=2e5+10,size=1<<20;

//char buf[size],*p1=buf,*p2=buf;
template<class o> void qr(o &x) {
	char c=gc; x=0; int f=1;
	while(!isdigit(c)){if(c=='-')f=-1; c=gc;}
	while(isdigit(c)) x=x*10+c-'0',c=gc;
	x*=f;
}
template<class o> void qw(o x) {
	if(x/10) qw(x/10);
	putchar(x%10+'0');
}
template<class o> void pr1(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); putchar(' ');
}
template<class o> void pr2(o x) {
	if(x<0)x=-x,putchar('-');
	qw(x); puts("");
}

int n,m,a[N],ans;

int main() {
	qr(n); qr(m); ans=0;
	for(int i=1;i<=n;i++) qr(a[i]),ans+=a[i];
	sort(a+1,a+n+1,greater<int>());
	if(a[m]*4LL*m>=ans) puts("Yes");
	else puts("No");
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>//solved by *ALIKHAN*
#define ll long long
#define ld long double
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
#define ppb pop_back
#define mp make_pair
#define all(n) n.begin(), n.end()
#define timefaster ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

const int N = (int)2e5 + 123;
const int mod = (int)1e9 + 7;
const int INF = (ll)1e18;

int main(){
	ll a,b,c;
	char q,w;
	cin >> a >> w >> b >> q >> c;
	if(a <= 2019 && b <= 4 && c <= 30){
		cout << "Heisei";
	} 
	else {
		cout << "TBD";
	}
}
// AKSAY SilA


Measured memory_bytes: 256
# include <bits/stdc++.h>

typedef long long ll;
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    vector<int> left(s.size() + 1);
    vector<int> right(s.size() + 1);
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '<') {
            left[i + 1] = left[i] + 1;
        } else {
            left[i + 1] = 0;
        }
    }
    for (int i = s.size() - 1; i >= 0; i--) {
        if (s[i] == '>') {
            right[i] = right[i + 1] + 1;
        } else {
            right[i] = 0;
        }
    }
    ll ans = 0;
    for (int i = 0; i <= s.size(); i++) {
        ans += max(right[i], left[i]);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 4764
/*
 * atcoder/abc115_2nd/c.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>
using namespace std;
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

const int MAX = 100100;
const ll INF = 100000000000000000;
int N, K;
ll A[MAX] = {0};
ll acc[MAX] = {0};

void solve() {
  cin >> N >> K;
  loop(n,0,N) cin >> A[n];
  sort(A, A+N);
  loop(n,1,N) {
    acc[n] = acc[n-1] + abs(A[n] - A[n-1]);
  }

  ll min_ = INF;
  for (int l=0; l+K<=N; l++) {
    // cout << acc[l+K-1] << " " << acc[l] << endl;
    chmin(min_, acc[l+K-1] - acc[l]);
  }
  cout << min_ << endl;
}
int main() {
  // cout.precision(15);
  // cout << fixed << double

  solve();

  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define FORR(i, m, n) for (int i = m; i >= n; i--)
#define ALL(x) (x).begin(), (x).end()
const long long INF = 1e18;
using namespace std;
typedef long long ll;
int main() {
  ll N;
  cin >> N;
  string s[N];
  REP(i, N) { cin >> s[i]; }

  map<string, ll> mp;
  REP(i, N) {
    vector<char> v;
    REP(j, 10) { v.push_back(s[i][j]); }
    sort(ALL(v));
    REP(j, 10) { s[i][j] = v[j]; }
    mp[s[i]]++;
  }
  ll ans = 0;
  for (auto x : mp) {
    ans += x.second * (x.second - 1) / 2;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 18176
//Utkarsh-raj

#include<bits/stdc++.h>

#define ll long long int
#define vc vector
#define mod 100000000007
#define mp make_pair
#define pb push_back
#define nl cout<<endl;
#define ff first
#define ss second

using namespace std;

// bool f(int k, int arr[], int n){
//     if(k == 0){
//         return false;
//     }

//     for(int i=0; i<n; i++){
//         if((k - arr[i] >= 0) && !f(k - arr[i], arr, n)){
//             return true;
//         }
//     }

//     return false;
// }

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ifstream myFile("task.in");
    if(!myFile.fail())
    {
        assert(freopen("task.in", "r", stdin));
    }

    int n, k;
    cin>>n>>k;

    int arr[n];
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }

    // if(f(k, arr, n)){
    //     cout<<"First"<<endl;
    // }
    // else{
    //     cout<<"Second"<<endl;
    // }




    vector<int> dp(k+1, 0);
    dp[0] = 0;

    for(int i=1; i <= k; i++){
        for(int j=0; j<n; j++){
            if((i - arr[j] >= 0) && !dp[i - arr[j]]){
                dp[i] = 1;
                break;
            }
        }
    }

    if(dp[k]){
        cout<<"First"<<endl;
    }
    else{
        cout<<"Second"<<endl;
    }

    return 0;
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
  
using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define uint unsigned int
#define ull  unsigned long long
#define pb push_back
#define mk make_pair
#define ins insert
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define X first
#define Y second
#define umap unordered_map
#define speed() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define setvalue(d,s,e,n) for(int qwe = s; qwe < e; ++qwe) d[qwe] = n
#define mset multiset
#define pqueue priority_queue
   
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
        
const int  N = 2e5 + 314;
const int INF = 1e9;
const double PI = acos(-1);
const int MOD = 1e9 + 7;
const double eps = 1e-9;
ll a[N];
 
ll bp(ll a, ll n) {
    ll res = 1;
    while(n) {
        if(n % 2)
            res = (res * a ) % MOD;
        a = (a * a) % MOD; 
        n /= 2;
    }
    return res;
}

void solve(){
    ll n, k;
    cin >> n >> k;
    ll ans = 0;
    for(int i = k; i >= 1; --i) {
        ll p = bp(k / i, n); 
        for(int j = 2 * i; j <= k; j += i) {
            p -= a[j];
            p += MOD;
            p %= MOD;
        }
        a[i] = p;
        ans += 1ll * p * i;
        ans %= MOD;
    }    
    cout << ans;
}

 
int main(){
    speed();
    int t = 1;
    // cin >> t;
    while(t--)solve();
}

Measured memory_bytes: 4408
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;

int main(){
    int N, tmp;
    map<int, int> dic;
    bool flg_dist = 1;

    std::cin >> N;

    for(int i = 0; i < N; i++){
        scanf("%d", &tmp);
    //    std::cout << tmp;
        if(dic.count(tmp)){
            flg_dist = 0;
            break;
        }else{
            dic[tmp] = 0;
        }
    }
    if(flg_dist == 1){
        std::cout << "YES";
    }else{
        std::cout << "NO";
    }
}

Measured memory_bytes: 12928
#include<stdio.h>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include<stack>
#include <queue>
#include<map>
#include <set>
#include<math.h>
using namespace std;
#define int long long
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define loop(i,m,n) for(ll i=m;i<n;++i)
#define ggr getchar(); getchar();return 0;
#define pie 3.141592653589793238462643383279
#define elif else if
#define P pair<ll,ll>
const int inf = 1000000007;
int bin(int bina) {
	int ans = 0;
	for (int i = 0; bina > 0; i++)
	{
		ans = ans + (bina % 2) * pow(10, i);
		bina = bina / 2;
	}
	return ans;
}
bool prime(int n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n % i == 0)return false;
	}
	return n != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x * y / gcd(x, y);
}
int kai(int x) {
	if (x == 0)return 1;
	return kai(x - 1) * x % inf;
}
int mod_pow(int x, int y, int mod) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	return kai(x)* mod_pow(kai(x - y), inf - 2, inf) % inf * mod_pow(kai(y), inf - 2, inf) % inf;
}
struct union_find {
	int par[200010], size_[200010];
	void init(int x) {
		rep(i, x) { par[i] = i; size_[i] = 1; }
	}
	int find(int x) {
		if (par[x] == x)return x;
		return par[x] = find(par[x]);
	}
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y)return;
		if (size_[x] < size_[y]) {
			par[x] = y;
			size_[y] += size_[x];
		}
		else {
			par[y] = x;
			size_[x] += size_[y];
		}
	}
};
char a[2005][2005];
int c[2005][2005];
signed main() {	
	int h, w;
	cin >> h >> w;
	rep(i, h) {
		rep(j, w) {
			cin >> a[i][j];
		}
	}
	rep(i, h) {
		int sum = 0;
		rep(j, w) {
			if (a[i][j] == '.') {
				sum++;
				c[i][j] += sum;
			}
			else sum = 0;
		}
		int su = 0;
		for (int j = w - 1; j > -1; --j) {
			if (a[i][j] == '.') {
				su++;
				c[i][j] += su;
				c[i][j] -= 1;
			}
			else su = 0;
		}
	}
	rep(j, w) {
		int iwa = 0;
		rep(i, h) {
			if (a[i][j] == '.') {
				iwa++;
				c[i][j] += iwa;
			}
			else iwa = 0;
		}
		int ta = 0;
		for (int i = h - 1; i > -1; --i) {
			if (a[i][j] == '.') {
				ta++;
				c[i][j] += ta;
				c[i][j] -= 1;
			}
			else ta = 0;
		}
	}
	int ans = 0;
	rep(i, h) {
		rep(j, w) {
			if (c[i][j] > ans) {
				ans = c[i][j];
			}
		}
	}
	cout << max((ll)0,ans-1) << endl;
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
#define db double 
#define maxn 200005 
#define mod 998244353
#define vi vector<double>
#define pb push_back
#define ll long long
using namespace std;
ll ksm(ll a, ll b) {
	if (!b) return 1;
	ll ns = ksm(a, b >> 1);
	ns = ns * ns % mod;
	if (b & 1) ns = ns * a % mod;
	return ns;
}
inline int add(int a, int b) {
	a += b;
	return (a < mod) ? a : (a - mod);
}
inline int sub(int a, int b) {
	a -= b;
	return (a < 0) ? a + mod : a;
}
inline int mul(int a, int b) {
	return (ll)a * b % mod;
}
// head

struct th {
	int id, num;
	th(int a, int b) {
		id = a, num = b;
	}
	bool operator < (const th &r)const {
		if (num != r.num) return num < r.num;
		return id < r.id;
	}
};
int a[maxn], b[maxn];	
int n;
int cal(int a) {
	a %= n;
	if (a == 0) return n;
	return a;
}
int main() {

	cin >> n;
	set<th> r;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) scanf("%d", &b[i]), r.insert(th(i, b[i]));
	ll cnt = 0;
	while (!r.empty()) {
		th u = *(--r.end());
		int nid = u.id;
		if (b[nid] != a[nid]) {
			int nr = b[nid], sm = b[cal(nid + 1)] + b[cal(nid - 1)], mx = max(b[cal(nid + 1)], b[cal(nid - 1)]);
			mx = max(mx, a[nid]);
			nr -= mx;
			int nd = (nr / sm);
			if (nr % sm) nd++;
			cnt += nd;
			if (!nd) {
				cout << -1 << endl;
				return 0;
			}
			b[nid] -= nd * sm;
		//	cout << "ACT" << nid << " " << b[nid] << endl;
			if (b[nid] < a[nid]) {
				cout << -1 << endl;
				return 0;
			}
			r.erase(u);
			r.insert(th(nid, b[nid]));
		}
		else r.erase(u);
	}
	cout << cnt << endl;
	return 0;
}


Measured memory_bytes: 11136
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sstream>
#include <iostream>
#include <math.h>
#include <time.h>
#include <unistd.h>
#include <algorithm>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <string>
 
#ifndef ONLINE_JUDGE
	#define DEBUG(x) cout << '>' << #x << ':' << x << endl;
#else
	#define DEBUG(x) do {} while(0);
#endif
 
#define pb push_back
#define mp make_pair
#define ALL(x) (x).begin(), (x).end()
#define PER(i, N) for(int (i) = (N)-1; (i) >= 0; (i)--)
#define REP(i, N) for(int (i) = 0; (i) < (int)(N); (i)++)
 
using namespace std;
typedef long long ll;
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }

template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }
const int MOD = 1000000007;
ll n,k;
ll dp[222222];
ll modpow(ll x,int pw) {
	if(pw == 0)return 1;
	if(pw==1) return x%MOD;
	ll hf = modpow(x,pw/2);
	hf = (hf*hf)%MOD;
	if(pw&1) hf = (hf*x)%MOD;
	return hf;
}
ll cnt(int G) {
	if(dp[G] ==-1) {
		int mults = 0;
		for(int j = G; j <= k; j += G)
			mults++;
		ll baseAns= modpow(mults, n);
		for(int j = 2*G; j <= k; j += G)
			baseAns = (MOD+(baseAns-cnt(j))%MOD)%MOD;
		dp[G] = baseAns;
	}
	return dp[G];
}

void solve(istream& cin, ostream& cout) {
	cin >>n>>k;
	memset(dp, -1, sizeof(dp));
	ll ans = 0;
	REP(i,k){
		(ans += ((cnt(i+1))*(i+1))%MOD)%=MOD;
	}
	cout <<ans<<endl;
}


int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	solve(cin, cout);
	/*
	{
		istringstream instr("2\n2\n14");
		solve(instr, cout);
	}
 */
	return 0;
}


Measured memory_bytes: 5392