INOI 2015 Periodic strings Problem

general
1

Can anyone tell me if my solution to the Periodic Strings problem from INOI 2015 is correct please? I can’t test it anywhere.

My Solution
Question paper

1 Like
2

Here is the official test data from last year’s INOI.

https://www.dropbox.com/s/0wn5pt9y9cm601w/PeriodicStrings-fulldata.zip?dl=0&preview=PeriodicStrings-fulldata.zip

2 Likes
3

Thank you!!! :slight_smile:

1 Like
4

i have a problem with this question… i dont see why this soltution of mine is wrong

#include<bits/stdc++.h>

using namespace std;



long long int power(int x,int a,int d)
{
	
	int i=0,b[1024],m,n;
    long long int ans=1;
	
	while(a!=0)
	{
		b[i]=a%2;
		a=a/2;
		i++;
	}
	n=i;
	for (int i=0;i<n;i++)
	{	
		if (b[i]==1)
		{
		ans=((ans%d)*(x%d))%d;
		}
		x=((x%d)*(x%d))%d;
	}
	
	return ans;
}

const long long int N=1e5+5;

long long int dp[N];


int main()
{
	long long int n,m,a=0;
	cin>>n>>m;
	dp[1]=1;
	for(int i=1; i<=n;i++)
	{
		for(int j=1;j<i;j++)
		{
			if(i%j==0)
			{
				a=(a+dp[j])%m;-
			}
		}
			dp[i]=(power(2,i,m)-a)%m;
			a=0;		
	}
	cout<<dp[n]%m<<endl;
	return 0;
}