川のブログ

川の適当気ままなブログです。 

AOJ 0142 Nature of Prime Numbers

こんにちは川です。

今回は、問題文にある通り計算していけばいいです。

 

自分用にメモリンクを張ります。

C++編(標準ライブラリ) 第21章 削除のアルゴリズム

 

ソースコード

 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,number[10001];
    for(int i=1;i<10000;i++)number[i]=i*i;
    while(cin>>n,n){
        vector<int> num;
        for(int i=1;i<n;i++)num.push_back(number[i]%n);
        sort(num.begin(),num.end());
        num.erase(unique(num.begin(),num.end()),num.end());
        int ans[5000]={};
        for(int i=0;i<num.size();i++){
            for(int j=0,k;j<num.size();j++){
                k=num[i]-num[j];
                if(k<0)k+=n;
                if(k>n/2)k=n-k;
                ans[k]++;
            }
        }
        for(int i=1;i<=n/2;i++)cout<<ans[i]<<endl;
    }
}