➤ 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!!