Pagini recente » Cod sursa (job #1646129) | Cod sursa (job #1763912) | Cod sursa (job #1441176) | Cod sursa (job #2318580) | Cod sursa (job #1169048)
#include <fstream>
#include <cstring>
#define maxn 1000001
using namespace std;
ifstream fin ("robotei.in");
ofstream fout ("robotei.out");
int G[maxn],reach[maxn],dist[maxn],ans[maxn],extra[maxn],cycle,n,m,M,modx,mody,X,Y,offx,offy,N;
int viz[maxn];
inline int node (int i, int j)
{
return m*i + j;
}
void dfs (int x)
{
viz[x] = cycle+1;
if (!viz[G[x]])
dfs (G[x]);
if (viz[G[x]] == cycle + 1)
{
dist[x] = dist[G[x]] + 1;
reach[x] = reach[G[x]];
}
else
{
dist[x] = 1;
reach[x] = viz[G[x]];
}
if (cycle && reach[x] && M - (cycle-reach[x]) - dist[x] > 0)
{
ans[1+ (M-(cycle-reach[x])-dist[x])/cycle]++;
if (extra[x])
{
if (M - (cycle-reach[x]) - dist[x] - 1> 0)
{
ans[1+ (M-(cycle-reach[x])-dist[x]-1)/cycle] += extra[x];
}
}
}
else if (!cycle && reach[x] == 2)
{
if (M >= dist[x])
ans[1] ++;
if (extra[x])
{
if (M - 1 >= dist[x])
{
ans[1] += extra[x];
}
}
}
}
int main()
{
fin>>n>>M>>X>>Y>>modx>>mody>>offx>>offy;
N = n;
m = n;
for (int i=0; i<n; ++i)
{
for (int j=mody; j<m; ++j)
{
extra[node((i*i+offx)%modx,(j*j+offy)%mody)]++;
}
}
for (int i=modx; i<n; ++i)
{
for (int j=0; j<m; ++j)
{
extra[node((i*i+offx)%modx,(j*j+offy)%mody)]++;
}
}
n = min (n,modx);
m = min (m,mody);
if (X > n || Y > m)
{
fout<<0<<" "<<1;
return 0;
}
for (int i=0; i<n; ++i)
{
for (int j=0; j<m; ++j)
{
G[node(i,j)] = node((i*i+offx)%modx,(j*j+offy)%mody);
}
}
cycle = 0;
for (int i=node(X,Y); ; i = G[i])
{
if (viz[i])
{
if (i != node(X,Y))
{
cycle = 0;
memset (viz,0,sizeof(viz));
viz[node(X,Y)] = 2;
}
break;
}
++cycle;
viz[i] = cycle;
}
if (cycle)
{
ans[1+M/cycle]++;
viz[node(X,Y)] = cycle;
if (extra[node(X,Y)])
{
if (M-1 > 0)
ans[1+(M-1)/cycle] += extra[node(X,Y)];
}
for (int x = G[node(X,Y)],cnt=1; x != node(X,Y); x = G[x],++cnt)
{
viz[x] = cnt;
if (M - (cycle-viz[x]) > 0)
{
ans[1 + (M-(cycle-viz[x]))/cycle]++;
}
if (extra[x])
{
if (M - (cycle-viz[x]) - 1 > 0)
{
ans[1 + (M-(cycle-viz[x])-1)/cycle] += extra[x];
}
}
}
}
else ans[1] ++;
for (int i=0; i<=n*m-1; ++i)
{
if (!viz[i])
dfs (i);
}
int s = 0;
for (int i=1; i <=M; ++i)
s += ans[i];
ans[0] = 1LL*N*N-s;
for (int i=0; i<=M; ++i)
{
if (ans[i])
fout<<i<<" "<<ans[i]<<"\n";
}
}