1061C. Multiplicity - Codeforces Solution C++

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