Pagini recente » Cod sursa (job #249189) | Cod sursa (job #329736) | Cod sursa (job #2166467) | Cod sursa (job #421660) | Cod sursa (job #1169067)
#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],extra[maxn],cnt1[maxn],cnt2[maxn],cycle,n,m,M,X,Y,offx,offy,N;
long long ans[maxn];
int viz[maxn];
inline int node (const int &i,const 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];
}
}
}
}
void extras ()
{
for (int i=0; i<n; ++i)
{
cnt1[(i*i+offx)%n] ++;
}
for (int j=m; j<N; ++j)
{
cnt2[(j*j+offy)%m] ++;
}
for (int i=0; i<n; ++i)
{
for (int j=0; j<m; ++j)
{
extra[node(i,j)] += cnt1[i]*cnt2[j];
}
}
memset (cnt1,0,sizeof(cnt1));
memset (cnt2,0,sizeof(cnt2));
for (int i=n; i<N; ++i)
{
cnt1[(i*i+offx)%n] ++;
}
for (int j=0; j<m; ++j)
{
cnt2[(j*j+offy)%m] ++;
}
for (int i=0; i<n; ++i)
{
for (int j=0; j<m; ++j)
{
extra[node(i,j)] += cnt1[i]*cnt2[j];
}
}
memset (cnt1,0,sizeof(cnt1));
memset (cnt2,0,sizeof(cnt2));
for (int i=n; i<N; ++i)
{
cnt1[(i*i+offx)%n] ++;
}
for (int j=m; j<N; ++j)
{
cnt2[(j*j+offy)%m] ++;
}
for (int i=0; i<n; ++i)
{
for (int j=0; j<m; ++j)
{
extra[node(i,j)] += cnt1[i]*cnt2[j];
}
}
}
int main()
{
fin>>N>>M>>X>>Y>>n>>m>>offx>>offy;
extras ();
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)%n,(j*j+offy)%m);
}
}
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);
}
long long 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";
}
}