2011-0058
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
简单来说，题目大意是，有一个等边三角形（边的内侧可以反射光线），顶点分别是A、B、C，一束光从A点沿某一固定角度射入，经过n次反射之后又从A点射出（注意光线可以从任一个顶点射出）。
问，给定n，有多少个射入角度（从A点射入）可以使光线恰好经过n次反射并最终从A点反射出。[[BR]]
解法：
把三角形扩展到整个平面，并建立一个斜角坐标系（AB为x轴正向，AC为y轴正向，夹角为60度），这样我们只需要在该坐标系的第一象限考虑问题。
首先所有点被分成三类，分别是A类，B类和C类（即分别对应不同顶点的反射像），不难发现(x,y)为A类点当且仅当((x%3==0&&(x+y)%3==0) 或者(x%3==1 && (x+y)%3==2)或者 (x%3==2 &&(x+y)%3==1)).[[BR]]
注意到若最终从(x,y)点射出，必然有gcd(x,y)=1，且反射次数为(x+y-1)+(x-1)+(y-1),三项分别是沿BC、AC和AB的反射次数[[BR]]
所以给定n，我们要求所有(x,y)点对的个数，满足[[BR]]
x>0,y>0,x+y=(n+3)/2,gcd(x,y)=1,(x,y)是A类点.[[BR]]
对(n+3)/2分解质因数,设为p1^s1^*p2^s2^*...*pt^st^.则求(n+3)/2以内满足条件的x（即所有不被p1,p2,...,pt整除且被3除余(3-((n+3)/2)%3)）的个数即可，容斥原理。
程序：
{{{
#include<iostream>
#include<set>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<cstdio>
using namespace std;
const int PSIZE = 200050;
long long plist[PSIZE], pcount = 0;
bool prime(long long n) {
if ((n != 2 && !(n % 2)) || (n != 3 && !(n % 3)) || (n != 5 && !(n % 5)) || (n != 7 && !(n % 7))) {
return false;
}
for (long long i = 0; plist[i] * plist[i] <= n; ++i) {
if (n % plist[i] == 0) {
return false;
}
}
return n > 1;
}
void initPrime() {
plist[pcount++] = 2;
for (long long i = 3; i < PSIZE; i += 2) {
if (prime(i)) {
plist[pcount++] = i;
}
}
}
long long primeFactor(long long n, long long * f, long long * nf) {
long long cnt = 0;
long long n2 = (long long) sqrt((double) n);
for (long long i = 0; n > 1 && plist[i] <= n2; ++i) {
if (n % plist[i] == 0) {
for (nf[cnt] = 0; n % plist[i] == 0; n /= plist[i]) {
++nf[cnt];
}
f[cnt++] = plist[i];
}
}
if (n > 1) {
nf[cnt] = 1;
f[cnt++] = n;
}
return cnt;
}
int main()
{
long long n;
initPrime();
while(scanf("%lld",&n)!=EOF)
{
if(n%2==0)
cout<<0<<endl;
else
{
long long t=(n+3)/2;
if(t%3!=0)
{
// a=2 mod(3)
long long f[20],nf[20];
long long num=primeFactor(t,f,nf);
long long tem=1;
long long ans=0;
//cout<<t<<" "<<num<<endl;
for(long long i=0;i<(1<<num);i++)
{
tem=1;
long long symbol=1;
for(long long j=0;j<num;j++)
{
if(i&(1<<j))
{
tem*=f[j];
symbol*=-1;
}
}
long long s=0;
if((tem%3==2&&t%3==1)||(tem%3==1&&t%3==2))
{
s=2;
}
else
s=1;
//cout<<tem<<endl;
ans+=symbol*((((t-1)/tem)+s)/3);
//cout<<symbol*(((t/tem)+1)/3)<<endl;
//cout<<endl;
}
cout<<ans<<endl;
}
else if(t%3==0)
{
cout<<0<<endl;
}
}
}
return 0;
}
}}}
by quietsmile简单来说，题目大意是，有一个等边三角形（边的内侧可以反射光线），顶点分别是A、B、C，一束光从A点沿某一固定角度射入，经过n次反射之后又从A点射出（注意光线可以从任一个顶点射出）。
问，给定n，有多少个射入角度（从A点射入）可以使光线恰好经过n次反射并最终从A点反射出。
解法：
把三角形扩展到整个平面，并建立一个斜角坐标系（AB为x轴正向，AC为y轴正向，夹角为60度），这样我们只需要在该坐标系的第一象限考虑问题。
首先所有点被分成三类，分别是A类，B类和C类（即分别对应不同顶点的反射像），不难发现(x,y)为A类点当且仅当((x%3==0&&(x+y)%3==0) 或者(x%3==1 && (x+y)%3==2)或者 (x%3==2 &&(x+y)%3==1)).
注意到若最终从(x,y)点射出，必然有gcd(x,y)=1，且反射次数为(x+y-1)+(x-1)+(y-1),三项分别是沿BC、AC和AB的反射次数
所以给定n，我们要求所有(x,y)点对的个数，满足
x>0,y>0,x+y=(n+3)/2,gcd(x,y)=1,(x,y)是A类点.
对(n+3)/2分解质因数,设为p1s1*p2s2*...*ptst.则求(n+3)/2以内满足条件的x（即所有不被p1,p2,...,pt整除且被3除余(3-((n+3)/2)%3)）的个数即可，容斥原理。
程序：
#include<iostream>
#include<set>
#include<map>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<cstdio>
using namespace std;
const int PSIZE = 200050;
long long plist[PSIZE], pcount = 0;
bool prime(long long n) {
if ((n != 2 && !(n % 2)) || (n != 3 && !(n % 3)) || (n != 5 && !(n % 5)) || (n != 7 && !(n % 7))) {
return false;
}
for (long long i = 0; plist[i] * plist[i] <= n; ++i) {
if (n % plist[i] == 0) {
return false;
}
}
return n > 1;
}
void initPrime() {
plist[pcount++] = 2;
for (long long i = 3; i < PSIZE; i += 2) {
if (prime(i)) {
plist[pcount++] = i;
}
}
}
long long primeFactor(long long n, long long * f, long long * nf) {
long long cnt = 0;
long long n2 = (long long) sqrt((double) n);
for (long long i = 0; n > 1 && plist[i] <= n2; ++i) {
if (n % plist[i] == 0) {
for (nf[cnt] = 0; n % plist[i] == 0; n /= plist[i]) {
++nf[cnt];
}
f[cnt++] = plist[i];
}
}
if (n > 1) {
nf[cnt] = 1;
f[cnt++] = n;
}
return cnt;
}
int main()
{
long long n;
initPrime();
while(scanf("%lld",&n)!=EOF)
{
if(n%2==0)
cout<<0<<endl;
else
{
long long t=(n+3)/2;
if(t%3!=0)
{
// a=2 mod(3)
long long f[20],nf[20];
long long num=primeFactor(t,f,nf);
long long tem=1;
long long ans=0;
//cout<<t<<" "<<num<<endl;
for(long long i=0;i<(1<<num);i++)
{
tem=1;
long long symbol=1;
for(long long j=0;j<num;j++)
{
if(i&(1<<j))
{
tem*=f[j];
symbol*=-1;
}
}
long long s=0;
if((tem%3==2&&t%3==1)||(tem%3==1&&t%3==2))
{
s=2;
}
else
s=1;
//cout<<tem<<endl;
ans+=symbol*((((t-1)/tem)+s)/3);
//cout<<symbol*(((t/tem)+1)/3)<<endl;
//cout<<endl;
}
cout<<ans<<endl;
}
else if(t%3==0)
{
cout<<0<<endl;
}
}
}
return 0;
}
by quietsmile