➤ Problem Link : 1061C. Multiplicity
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define m 1000000007
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll n;
cin>>n;
ll arr[n+1];
ll dp[n+1]={0};
ll ct[n+1]={0};
unordered_map<ll,unordered_set<ll> > mp;
for(ll i=1;i<=n;i++)
cin>>arr[i];
dp[0]=1;
for(ll i=1;i<=n;i++)
{
unordered_set<ll> ck;
if(mp.find(arr[i])!=mp.end())
{
ck=mp[arr[i]];
for(auto it= ck.begin();it!=ck.end();it++)
{
if(*it <= i)
ct[*it]=(dp[*it]+dp[*it - 1])%m;
}
}
else
{
for(ll j=1;j*j<=arr[i];j++)
{
if(arr[i]%j==0){
if(j<=i)
ct[j]=(dp[j]+dp[j-1])%m;
ck.insert(j);
}
if(arr[i]/j==j)
break;
if(arr[i]%(arr[i]/j)==0)
{
if((arr[i]/j)<=i )
ct[arr[i]/j]=(dp[arr[i]/j]+dp[(arr[i]/j)-1])%m;
ck.insert(arr[i]/j);
}
}
mp[arr[i]]=ck;
}
for(auto it= ck.begin();it!=ck.end();it++)
{
if(*it <= i)
dp[(*it)]=ct[(*it)];
}
/* for(ll j=1;j*j<=arr[i];j++)
{
if(arr[i]%j==0 && j<=i)
dp[j]=ct[j];
if(arr[i]==1)
continue;
if(arr[i]%(arr[i]/j)==0 && (arr[i]/j)<=i )
dp[arr[i]/j]=ct[arr[i]/j];
}*/
// cout<<dp[1]<<" "<<dp[2]<<endl;
}
ll ans=0;
for(ll i=1;i<=n;i++)
ans=(ans+dp[i])%m;
cout<<ans;
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.