PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Seemanta Bhattacharjee
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
2527
PREREQUISITES:
Combinatorics, GCD and LCM
PROBLEM:
Given an array A of N integers. Find the number of different subsequences of the array that follow these conditions:
- For any two numbers a, b in the subsequence: lcm(l, a) - a = lcm(l, b) - b. Here, l is the length of the subsequence.
- l > 1, l is the length of the subsequence.
Since the answer can be very long, print it modulo 10^9+7.
Subsequence of an array can be obtained by erasing some (possibly zero) elements from the array. Two subsequences are considered different if one of them contains an index i that the other one doesn’t.
EXPLANATION:
Subsequences that are consisted of a single value are always good, so let’s consider subsequences with two or more values. Let’s consider two values a and b first, and see which conditions should l have.
WLOG, let a > b. We see that lcm(a, l) - a = lcm(b, l) - b \Rightarrow l \cdot (a / gcd(a, l) - b / gcd(b, l)) = a - b, where we used the identity lcm(x, y) = x \cdot y / gcd(x, y). Therefore, l divides a - b. Let kl = a - b for some integer k, then a = b + kl, then gcd(a, l) = gcd(b + kl, l) = gcd(b, l). Let gcd(a, l) = gcd(b, l) = g, then l \cdot (a / g - b / g) = a - b \Rightarrow l = g, or l = lcm(a, l) = lcm(b, l), which means l divides both a and b.
Extending from this condition, in general, a subsequence is good iff:
- All values in the subsequence are equal, or
- Length of the subsequence divides every value in the subsequence.
The solution from here is quite simple: for case 2, for each length l from 2 to N, we count the number of values that is divisible by l (let this value be cnt_l). Then the number of possible subsequences of length l of case 2 is \binom{cnt_l}{l}; while for case 1, let the occurence of each value be occ_v, then its contribution to the answer is 2^{occ_v} - 1 - occ_v. Be careful of the overlap between case 1 and case 2.
TIME COMPLEXITY:
Time complexity is O(N \sqrt{\max(A)}) for each test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;
const int mod = 1e9 + 7;
int tc, cs = 1;
string to_string(string s) {
return '"' + s + '"';
}
string to_string(const char* s) {
return to_string((string) s);
}
string to_string(bool b) {
return (b ? "true" : "false");
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
bool first = true;
string res = "{";
for (const auto &x : v) {
if (!first) {
res += ", ";
}
first = false;
res += to_string(x);
}
res += "}";
return res;
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
cerr << " " << to_string(H);
debug_out(T...);
}
#ifndef ONLINE_JUDGE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
int n, a[N];
unordered_map<int, int> cnt, freq;
ll f[N], If[N], pw[N];
ll bigmod(ll a, ll n, ll M) {
ll res = 1LL;
while (n) {
if (n & 1) res = (res * a) % M;
a = (a * a) % M;
n >>= 1;
}
return res % M;
}
ll Inverse(ll n) {
return bigmod(n, mod-2, mod);
}
ll nCr(ll n,ll r) {
if (n < r) return 0;
return (((f[n] * If[r]) % mod) * If[n-r]) % mod;
}
void prec() {
f[0] = 1, If[0] = 1;
f[1] = 1, If[1] = 1;
for (int i = 2; i <= N - 10; ++i){
f[i] = (f[i-1] * 1LL * i) % mod;
If[i] = ((Inverse(i) * If[i-1]) % mod);
}
}
void test_cases() {
cnt.clear(); freq.clear();
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], freq[a[i]]++;
ll ans = 0;
for (auto p: freq) {
ll f = p.second;
ans = (ans + pw[f]) % mod;
ans = (ans - (f + 1) + mod) % mod;
for (int j = 1; j*j <= p.first; ++j) {
if (p.first % j == 0) {
cnt[j] += f;
if (j > 1) ans = (ans - nCr(f, j) + mod) % mod;
if (((p.first/j) != j) && p.first/j <= n) {
cnt[p.first/j] += f;
if (p.first/j > 1) ans = (ans - nCr(f, p.first/j) + mod) % mod;
}
}
}
}
for (int len = 2; len <= n; ++len) {
ans = (ans + nCr(cnt[len], len)) % mod;
} cout << ans << '\n';
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
prec();
pw[0] = 1;
for (int i = 1; i <= N-10; ++i) pw[i] = (pw[i - 1] * 2LL) % mod;
cin >> tc;
while (tc--) {
test_cases();
}
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=1e9+7;
const int iu=1e7;
const int ty=1e5;
ll f[100001],inf[100001],p2[100001];
ll pw(ll x,ll y){
if(y==0) return 1;
if(y%2) return x*pw(x,y-1)%mod;
ll res=pw(x,y/2);
return res*res%mod;
}
ll C(ll x,ll y){
if(x<y) return 0;
return f[x]*inf[y]%mod*inf[x-y]%mod;
}
int sp[iu+1];
int pc=0;
int ps[iu+1];
int n;
int a[100001];
int f1[iu+1],f2[iu+1];
int bs=0;
int bin[iu+1];
ll ans=0;
void get(int x,int w,int king){
//cout << "get " << x << ' ' << w << ' ' << king << endl;
if(x==1){
if(++f1[w]==1) bin[++bs]=w;
if(w!=1) ans=(ans+mod-C(f2[king],w-1));
return;
}
int p=sp[x];
get(x/p,w,king);
while(x%p==0){
w*=p;x/=p;
}
//cout << x << ' ' << w << ' ' << king <<' ' << p << endl;
get(x,w,king);
}
void solve(){
cin >> n;ans=0;bs=0;
for(int i=1; i<=n ;i++){
cin >> a[i];
get(a[i],1,a[i]);
f2[a[i]]++;
}
for(int i=1; i<=bs ;i++){
int x=bin[i];
//cout << "! " << x << ' ' << f1[x] << endl;
if(x!=1) ans=(ans+C(f1[x],x))%mod;
ans=(ans+p2[f2[x]]-f2[x]-1+mod)%mod;
f1[x]=f2[x]=0;
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
f[0]=1;p2[0]=1;
for(int i=1; i<=ty ;i++) f[i]=f[i-1]*i%mod,p2[i]=p2[i-1]*2%mod;
inf[ty]=pw(f[ty],mod-2);
for(int i=ty; i>=1 ;i--) inf[i-1]=inf[i]*i%mod;
for(int i=2; i<=iu ;i++){
if(sp[i]==0){
sp[i]=i;
ps[++pc]=i;
}
for(int j=1; ps[j]<=sp[i] && ps[j]*i<=iu && j<=pc ;j++){
sp[ps[j]*i]=ps[j];
}
}
int t;cin >> t;while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using namespace atcoder;
const int MX = 1E5 + 5;
using mint = modint1000000007;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
vector<mint> fct(MX);
fct[0] = 1;
for (int i = 1; i < MX; i++) {
fct[i] = fct[i - 1] * i;
}
auto C = [&](int n, int k) {
return n < k || k < 0 ? mint(0) : fct[n] / fct[k] / fct[n - k];
};
while (t--) {
int n; cin >> n;
map<int, int> occ;
vector<int> len(n + 1);
for (int i = 0; i < n; i++) {
int u; cin >> u;
occ[u]++;
}
mint ans = 0;
for (auto [val, cnt] : occ) {
ans += mint(2).pow(cnt) - 1;
for (int i = 1; i * i <= val; i++) {
if (val % i == 0 && i <= n) {
len[i] += cnt;
ans -= C(cnt, i);
if (val / i != i && val / i <= n) {
len[val / i] += cnt;
ans -= C(cnt, val / i);
}
}
}
}
for (int i = 2; i <= n; i++) {
ans += C(len[i], i);
}
cout << ans.val() << '\n';
}
}
I tried to submit many times using naive method to calculate divisors and also by using O(Amax*log(Amax)), I was getting TLE in both.