下面l出我的解法Q几乎可以一步到位求出来
实现代码如下Q?br />/**
*Author: Koth (http://weibo.com/yovn)
*Date: 2011-12-01
*/
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
int solve(int Y,int& X){
int m=0;
int t=Y;
if(Y<=0){
X=Y;
return 1;
}
while((t&1)==0){
m+=1;
t=t>>1;
}
if(m==32){
X=Y;
return 1;
}
int lastK=32;
for(;lastK>m+1;lastK--){
if(Y &(1<<(lastK-1))){
break;
}
}
//its a number st. exp(2,K)
if(lastK==(m+1)){
X=Y;
return 1;
}
int k=1<<(m+1);
int b=(Y>>m)-(1<<(lastK-m-1));
X=(1<<(lastK-m-2))+(b+1-k)/2;
if(X<=0){
k=k-1-((0-X)<<1);
X=0-X+1;
}
return k;
}
int main(int argc,char* argv[]){
if(argc<=1){
fprintf(stdout,"Usage:%s number\n",argv[0]);
return 0;
}
int Y=atoi(argv[1]);
int X=0;
int k=solve(Y,X);
fprintf(stdout,"%d=",Y);
for(int i=0;i<k;i++){
fprintf(stdout,"%d",X+i);
if(i<(k-1)){
fprintf(stdout,"+");
}
}
fprintf(stdout,"\n");
return 0;
}
*Author: Koth (http://weibo.com/yovn)
*Date: 2011-12-01
*/
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
int solve(int Y,int& X){
int m=0;
int t=Y;
if(Y<=0){
X=Y;
return 1;
}
while((t&1)==0){
m+=1;
t=t>>1;
}
if(m==32){
X=Y;
return 1;
}
int lastK=32;
for(;lastK>m+1;lastK--){
if(Y &(1<<(lastK-1))){
break;
}
}
//its a number st. exp(2,K)
if(lastK==(m+1)){
X=Y;
return 1;
}
int k=1<<(m+1);
int b=(Y>>m)-(1<<(lastK-m-1));
X=(1<<(lastK-m-2))+(b+1-k)/2;
if(X<=0){
k=k-1-((0-X)<<1);
X=0-X+1;
}
return k;
}
int main(int argc,char* argv[]){
if(argc<=1){
fprintf(stdout,"Usage:%s number\n",argv[0]);
return 0;
}
int Y=atoi(argv[1]);
int X=0;
int k=solve(Y,X);
fprintf(stdout,"%d=",Y);
for(int i=0;i<k;i++){
fprintf(stdout,"%d",X+i);
if(i<(k-1)){
fprintf(stdout,"+");
}
}
fprintf(stdout,"\n");
return 0;
}
]]>
]]>
但是要注意，IOCP工作U程的线E池必须?Fix的，因ؓ你发出的dh都关联到相应的线E上Q如果线E死了，那读写完成情冉|不知道的?br />
作ؓ一个Http ServerQ传送文件是必不可少的功能，那一般文件的传送都是要把程序里的buffer拯到内核的bufferQ由内核发送出ȝ。windowsq_上ؓq种情况提供了很好的解决ҎQ用TransmitFile接口
BOOL TransmitFile(
SOCKET hSocket,
HANDLE hFile,
DWORD nNumberOfBytesToWrite,
DWORD nNumberOfBytesPerSend,
LPOVERLAPPED lpOverlapped,
LPTRANSMIT_FILE_BUFFERS lpTransmitBuffers,
DWORD dwFlags
);
SOCKET hSocket,
HANDLE hFile,
DWORD nNumberOfBytesToWrite,
DWORD nNumberOfBytesPerSend,
LPOVERLAPPED lpOverlapped,
LPTRANSMIT_FILE_BUFFERS lpTransmitBuffers,
DWORD dwFlags
);
你只要把文g句柄发送给内核p了，内核帮你搞定其余的，真正做到Zero-Copy.
但是很不q，NIO2里AsynchronousSocketChannel没有提供q样的支持。而ؓHTTP Server的性能考量Q本人只好自己增加这个支持?br />
要无~支持，q个必须得表现的?Read /Write一P有完成的通知Q通知传送多数据，{等?br />
仔细dsun的IOCP实现以后发现q部分工作他们封装得很好Q基本只要往他们的框枉加东西就好了?br /> Z能访问他们的框架代码Q我定义自己的TransmitFile支持cdsun.nio.ch包里Q以获得最大的权限?br />
package sun.nio.ch;
import java.io.IOException;
import java.lang.reflect.Field;
import java.nio.channels.AsynchronousCloseException;
import java.nio.channels.AsynchronousSocketChannel;
import java.nio.channels.ClosedChannelException;
import java.nio.channels.CompletionHandler;
import java.nio.channels.NotYetConnectedException;
import java.nio.channels.WritePendingException;
import java.util.concurrent.Future;
/**
* @author Yvon
*
*/
public class WindowsTransmitFileSupport {
//Sun's NIO2 channel implementation class
private WindowsAsynchronousSocketChannelImpl channel;
//nio2 framework core data structure
PendingIoCache ioCache;
//some field retrieve from sun channel implementation class
private Object writeLock;
private Field writingF;
private Field writeShutdownF;
private Field writeKilledF; // f
WindowsTransmitFileSupport()
{
//dummy one for JNI code
}
/**
*
*/
public WindowsTransmitFileSupport(
AsynchronousSocketChannel
channel) {
this.channel = (WindowsAsynchronousSocketChannelImpl)channel;
try {
// Initialize the fields
Field f = WindowsAsynchronousSocketChannelImpl.class
.getDeclaredField("ioCache");
f.setAccessible(true);
ioCache = (PendingIoCache) f.get(channel);
f = AsynchronousSocketChannelImpl.class
.getDeclaredField("writeLock");
f.setAccessible(true);
writeLock = f.get(channel);
writingF = AsynchronousSocketChannelImpl.class
.getDeclaredField("writing");
writingF.setAccessible(true);
writeShutdownF = AsynchronousSocketChannelImpl.class
.getDeclaredField("writeShutdown");
writeShutdownF.setAccessible(true);
writeKilledF = AsynchronousSocketChannelImpl.class
.getDeclaredField("writeKilled");
writeKilledF.setAccessible(true);
} catch (NoSuchFieldException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (SecurityException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IllegalArgumentException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IllegalAccessException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
/**
* Implements the task to initiate a write and the handler to consume the
* result when the send file completes.
*/
private class SendFileTask<V, A> implements Runnable, Iocp.ResultHandler {
private final PendingFuture<V, A> result;
private final long file;//file is windows file HANDLE
SendFileTask(long file, PendingFuture<V, A> result) {
this.result = result;
this.file = file;
}
@Override
// @SuppressWarnings("unchecked")
public void run() {
long overlapped = 0L;
boolean pending = false;
boolean shutdown = false;
try {
channel.begin();
// get an OVERLAPPED structure (from the cache or allocate)
overlapped = ioCache.add(result);
int n = transmitFile0(channel.handle, file, overlapped);
if (n == IOStatus.UNAVAILABLE) {
// I/O is pending
pending = true;
return;
}
if (n == IOStatus.EOF) {
// special case for shutdown output
shutdown = true;
throw new ClosedChannelException();
}
// write completed immediately
throw new InternalError("Write completed immediately");
} catch (Throwable x) {
// write failed. Enable writing before releasing waiters.
channel.enableWriting();
if (!shutdown && (x instanceof ClosedChannelException))
x = new AsynchronousCloseException();
if (!(x instanceof IOException))
x = new IOException(x);
result.setFailure(x);
} finally {
// release resources if I/O not pending
if (!pending) {
if (overlapped != 0L)
ioCache.remove(overlapped);
}
channel.end();
}
// invoke completion handler
Invoker.invoke(result);
}
/**
* Executed when the I/O has completed
*/
@Override
@SuppressWarnings("unchecked")
public void completed(int bytesTransferred, boolean canInvokeDirect) {
// release waiters if not already released by timeout
synchronized (result) {
if (result.isDone())
return;
channel.enableWriting();
result.setResult((V) Integer.valueOf(bytesTransferred));
}
if (canInvokeDirect) {
Invoker.invokeUnchecked(result);
} else {
Invoker.invoke(result);
}
}
@Override
public void failed(int error, IOException x) {
// return direct buffer to cache if substituted
// release waiters if not already released by timeout
if (!channel.isOpen())
x = new AsynchronousCloseException();
synchronized (result) {
if (result.isDone())
return;
channel.enableWriting();
result.setFailure(x);
}
Invoker.invoke(result);
}
}
public <V extends Number, A> Future<V> sendFile(long file, A att,
CompletionHandler<V, ? super A> handler) {
boolean closed = false;
if (channel.isOpen()) {
if (channel.remoteAddress == null)
throw new NotYetConnectedException();
// check and update state
synchronized (writeLock) {
try{
if (writeKilledF.getBoolean(channel))
throw new IllegalStateException(
"Writing not allowed due to timeout or cancellation");
if (writingF.getBoolean(channel))
throw new WritePendingException();
if (writeShutdownF.getBoolean(channel)) {
closed = true;
} else {
writingF.setBoolean(channel, true);
}
}catch(Exception e)
{
IllegalStateException ise=new IllegalStateException(" catch exception when write");
ise.initCause(e);
throw ise;
}
}
} else {
closed = true;
}
// channel is closed or shutdown for write
if (closed) {
Throwable e = new ClosedChannelException();
if (handler == null)
return CompletedFuture.withFailure(e);
Invoker.invoke(channel, handler, att, null, e);
return null;
}
return implSendFile(file,att,handler);
}
<V extends Number, A> Future<V> implSendFile(long file, A attachment,
CompletionHandler<V, ? super A> handler) {
// setup task
PendingFuture<V, A> result = new PendingFuture<V, A>(channel, handler,
attachment);
SendFileTask<V,A> sendTask=new SendFileTask<V,A>(file,result);
result.setContext(sendTask);
// initiate I/O (can only be done from thread in thread pool)
// initiate I/O
if (Iocp.supportsThreadAgnosticIo()) {
sendTask.run();
} else {
Invoker.invokeOnThreadInThreadPool(channel, sendTask);
}
return result;
}
private native int transmitFile0(long handle, long file,
long overlapped);
}
q个操作跟默认实现的里的write操作是很像的Q只是最后调用的本地Ҏ不一栗?br />
接下来，我们怎么使用呢，q个cL定义在sun的包里的Q直接用的话Q会报IllegalAccessError,因ؓ我们的类加蝲器跟初始化加载器是不一L?br /> 解决办法一个是通过启动参数-XbootclasspathQ让我们的包被初始加载器加蝲。我个h不喜Ƣ这U办法，所以就采用JNI来定义我们的windows TransmitFile支持cR?br />
q样我们的工作算是完成了Q注意，发送文件的时候传得是文g句柄Q这样做的好处是你可以更好的控制Q一般是在发送前Q打开文g句柄Q完成后在回调通知Ҏ里关闭文件句柄?br />
有兴的同学可以看看我的HTTP server目:
http://code.google.com/p/jabhttpd/
目前基本功能实现得差不多Q做了些单的试Q性能比较满意。这个服务器不打支持servlet apiQ基本是专门l做Z长连接模式通信的定做的?br />
]]>
Command Network
Description
After a long lasting war on words, a war on arms finally breaks out between littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered a total failure of littleken’s command network. A provisional network must be built immediately. littleken orders snoopy to take charge of the project.
With the situation studied to every detail, snoopy believes that the most urgent point is to enable littenken’s commands to reach every disconnected node in the destroyed network and decides on a plan to build a unidirectional communication network. The nodes are distributed on a plane. If littleken’s commands are to be able to be delivered directly from a node A to another node B, a wire will have to be built along the straight line segment connecting the two nodes. Since it’s in wartime, not between all pairs of nodes can wires be built. snoopy wants the plan to require the shortest total length of wires so that the construction can be done very soon.
Input
The input contains several test cases. Each test case starts with a line containing two integer N (N ≤ 100), the number of nodes in the destroyed network, and M (M ≤ 104), the number of pairs of nodes between which a wire can be built. The next N lines each contain an ordered pair xi and yi, giving the Cartesian coordinates of the nodes. Then follow M lines each containing two integers i and j between 1 and N (inclusive) meaning a wire can be built between node i and node j for unidirectional command delivery from the former to the latter. littleken’s headquarter is always located at node 1. Process to end of file.
Output
For
each test case, output exactly one line containing the shortest total
length of wires to two digits past the decimal point. In the cases that
such a network does not exist, just output ‘poor snoopy’.
一开始没仔细读题Q一看以为是最生成树呢，l果Krusal法上去WA了，Prim法也WA,修修Ҏ一直WAQ第二天发现本题是要在有向图上面构造最树形图?br />
按照著名的Zhu-Liu法Q仔l实C一边，l于AC了?br /> 按照我的理解ȝ下该法Q该法Ҏ个结点，除根节点外寻找最入边，
1Q如果这些入边不构成环，那么Ҏ证明q些Ҏ成最树形图?br /> 证明Q设加上根节点r一共N个点Q那么一共有N-1条边Q证明从r能到每个点，若存在一点vQ得从r到v没有路径Q那么，假设从v反向回退必然构成环，因ؓ每个炚w了r都有入边Q如果不构成环，该\径可以无I大?br /> 2Q如果存在环Q我们把环收~成一个点Q更新相应的入边和出边，得到新的图G',使得原问题在G'中等效：
怎么收羃呢？
假设我们把环收羃成环上的L一点vQ所有进环的边和出环的边自动变成v的边Q如果已有，取长度最短的Q，其余ҎCؓ删除Q更C在环上的所有点q入该环的长度cost为cost-cost(prev[x],x);其中点x入环的边在环上的端点。出边保持不变?br />
q里Z么这么更斎ͼ因ؓq样更新使得我们的算法在新图上是{效的。Q何环的解军_意味着在新N面得为改收羃后的点寻找新的入边，而实际的p应该是新的入边减d有的入边长度Q我们的法在找到环的时候就把环上所有的边的长度计算在花费内?而对是没有媄响的?br />
到这法的框架基本出来了。当为某Ҏ扑ֈ入边的时候，意味着无解。ؓ了加快无解的侦测Q我们先q行一遍DFS搜烦Q假如从根节点出发，可触及的节点数小于N-1(不含r)则意味着无解。反之，肯定有解?
Z么？
因ؓ如果可触及数于N-1,意味着某点是不可触及的Q也是原图不是p通。对该点来说不存在从r到它的\径。反之，从r到某炚w有一条\径，沿着该\径就能找到结点的入边?br />
W二个问题是Q如何快速侦环呢？
我用了一个不怺集。回忆Krusal的算法实现里面也是用不怺集来避免找生环的最边?br />
下面是我的代码：
// 3164.cpp : Defines the entry point for the console application.
//
#include <iostream>
#include <cmath>
using namespace std;
typedef struct _Point
{
double x;
double y;
double distanceTo(const struct _Point& r)
{
return sqrt((x-r.x)*(x-r.x)+(y-r.y)*(y-r.y));
}
}Point;
const int MAX_V=100;
const int MAX_E=10000;
const double NO_EDGE=1.7976931348623158e+308;
Point vertexes[MAX_V]={0};
int parents[MAX_V]={0};
int ranks[MAX_V]={0};
double G[MAX_V][MAX_V]={0};
bool visited[MAX_V]={0};
bool deleted[MAX_V]={0};
int prev[MAX_V]={0};
int nVertex=0;
int nEdge=0;
int u_find(int a)
{
if(parents[a]==a)return a;
parents[a]=u_find(parents[a]);
return parents[a];
}
void u_union(int a,int b)
{
int pa=u_find(a);
int pb=u_find(b);
if(ranks[pa]==ranks[pb])
{
ranks[pa]++;
parents[pb]=pa;
}else if(ranks[pa]<ranks[pb])
{
parents[pa]=pb;
}
else
{
parents[pb]=pa;
}
}
void DFS(int v,int& c)
{
visited[v]=true;
for(int i=1;i<nVertex;i++)
{
if(!visited[i]&&G[v][i]<NO_EDGE)
{
c+=1;
DFS(i,c);
}
}
}
void doCycle(int s,int t,double& cost)
{
memset(visited,0,sizeof(bool)*nVertex);
int i=s;
do
{
visited[i]=true;
cost+=G[prev[i]-1][i];
//cout<<"from "<<(prev[i]-1)<<" to "<<i<<" (cycle)"<<" weight:"<<G[prev[i]-1][i]<<endl;
i=prev[i]-1;
}while(i!=s);
do
{
for(int k=0;k<nVertex;k++)
{
if(!deleted[k]&&!visited[k])
{
if(G[k][i]<NO_EDGE)
{
if(G[k][i]-G[prev[i]-1][i]<G[k][s])
{
G[k][s]=G[k][i]-G[prev[i]-1][i];
//cout<<"1.update ["<<k<<","<<s<<"] at "<<i<<" as "<<G[k][s]<<endl;
}
}
if(G[i][k]<NO_EDGE)
{
if(G[i][k]<G[s][k])
{
G[s][k]=G[i][k];
//cout<<"2.update ["<<s<<","<<k<<"] at "<<i<<" as "<<G[s][k]<<endl;
}
}
}
}
if(i!=s)
{
deleted[i]=true;
//cout<<"mark "<<i<<" as deleted"<<endl;
}
i=prev[i]-1;
}while(i!=s);
}
int main(void)
{
while(cin>>nVertex>>nEdge)
{
int s,t;
int nv=0;
bool cycle=0;
double cost=0;
memset(vertexes,0,sizeof(vertexes));
memset(visited,0,sizeof(visited) );
memset(deleted,0,sizeof(deleted));
memset(G,0,sizeof(G));
memset(prev,0,sizeof(prev));
memset(ranks,0,sizeof(ranks));
memset(parents,0,sizeof(parents));
for(int i=0;i<nVertex;i++)
{
cin>>vertexes[i].x>>vertexes[i].y;
parents[i]=i;
for(int j=0;j<nVertex;j++)
{
G[i][j]=NO_EDGE;
}
}
for(int i=0;i<nEdge;i++)
{
cin>>s>>t;
if(t==1||s==t)continue;
G[s-1][t-1]=vertexes[s-1].distanceTo(vertexes[t-1]);
}
DFS(0,nv);
if(nv<nVertex-1)
{
cout<<"poor snoopy"<<endl;
continue;
}
do {
cycle=false;
for(int i=0;i<nVertex;i++){parents[i]=i;}
memset(ranks,0,sizeof(bool)*nVertex);
for (int i = 1; i < nVertex; i++) {
double minimum=NO_EDGE;
if(deleted[i])continue;
for(int k=0;k<nVertex;k++)
{
if(!deleted[k]&&minimum>G[k][i])
{
prev[i]=k+1;
minimum=G[k][i];
}
}
if(minimum==NO_EDGE)
{
throw 1;
}
if (u_find(prev[i]-1) == u_find(i)) {
doCycle(prev[i]-1,i, cost);
cycle = true;
break;
}
else
{
u_union(i,prev[i]-1);
}
}
} while (cycle);
for (int i = 1; i < nVertex; i++) {
if(!deleted[i])
{
cost+=G[prev[i]-1][i];
//cout<<"from "<<(prev[i]-1)<<" to "<<i<<" weight:"<<G[prev[i]-1][i]<<endl;
}
}
printf("%.2f\n",cost);
}
}
//
#include <iostream>
#include <cmath>
using namespace std;
typedef struct _Point
{
double x;
double y;
double distanceTo(const struct _Point& r)
{
return sqrt((x-r.x)*(x-r.x)+(y-r.y)*(y-r.y));
}
}Point;
const int MAX_V=100;
const int MAX_E=10000;
const double NO_EDGE=1.7976931348623158e+308;
Point vertexes[MAX_V]={0};
int parents[MAX_V]={0};
int ranks[MAX_V]={0};
double G[MAX_V][MAX_V]={0};
bool visited[MAX_V]={0};
bool deleted[MAX_V]={0};
int prev[MAX_V]={0};
int nVertex=0;
int nEdge=0;
int u_find(int a)
{
if(parents[a]==a)return a;
parents[a]=u_find(parents[a]);
return parents[a];
}
void u_union(int a,int b)
{
int pa=u_find(a);
int pb=u_find(b);
if(ranks[pa]==ranks[pb])
{
ranks[pa]++;
parents[pb]=pa;
}else if(ranks[pa]<ranks[pb])
{
parents[pa]=pb;
}
else
{
parents[pb]=pa;
}
}
void DFS(int v,int& c)
{
visited[v]=true;
for(int i=1;i<nVertex;i++)
{
if(!visited[i]&&G[v][i]<NO_EDGE)
{
c+=1;
DFS(i,c);
}
}
}
void doCycle(int s,int t,double& cost)
{
memset(visited,0,sizeof(bool)*nVertex);
int i=s;
do
{
visited[i]=true;
cost+=G[prev[i]-1][i];
//cout<<"from "<<(prev[i]-1)<<" to "<<i<<" (cycle)"<<" weight:"<<G[prev[i]-1][i]<<endl;
i=prev[i]-1;
}while(i!=s);
do
{
for(int k=0;k<nVertex;k++)
{
if(!deleted[k]&&!visited[k])
{
if(G[k][i]<NO_EDGE)
{
if(G[k][i]-G[prev[i]-1][i]<G[k][s])
{
G[k][s]=G[k][i]-G[prev[i]-1][i];
//cout<<"1.update ["<<k<<","<<s<<"] at "<<i<<" as "<<G[k][s]<<endl;
}
}
if(G[i][k]<NO_EDGE)
{
if(G[i][k]<G[s][k])
{
G[s][k]=G[i][k];
//cout<<"2.update ["<<s<<","<<k<<"] at "<<i<<" as "<<G[s][k]<<endl;
}
}
}
}
if(i!=s)
{
deleted[i]=true;
//cout<<"mark "<<i<<" as deleted"<<endl;
}
i=prev[i]-1;
}while(i!=s);
}
int main(void)
{
while(cin>>nVertex>>nEdge)
{
int s,t;
int nv=0;
bool cycle=0;
double cost=0;
memset(vertexes,0,sizeof(vertexes));
memset(visited,0,sizeof(visited) );
memset(deleted,0,sizeof(deleted));
memset(G,0,sizeof(G));
memset(prev,0,sizeof(prev));
memset(ranks,0,sizeof(ranks));
memset(parents,0,sizeof(parents));
for(int i=0;i<nVertex;i++)
{
cin>>vertexes[i].x>>vertexes[i].y;
parents[i]=i;
for(int j=0;j<nVertex;j++)
{
G[i][j]=NO_EDGE;
}
}
for(int i=0;i<nEdge;i++)
{
cin>>s>>t;
if(t==1||s==t)continue;
G[s-1][t-1]=vertexes[s-1].distanceTo(vertexes[t-1]);
}
DFS(0,nv);
if(nv<nVertex-1)
{
cout<<"poor snoopy"<<endl;
continue;
}
do {
cycle=false;
for(int i=0;i<nVertex;i++){parents[i]=i;}
memset(ranks,0,sizeof(bool)*nVertex);
for (int i = 1; i < nVertex; i++) {
double minimum=NO_EDGE;
if(deleted[i])continue;
for(int k=0;k<nVertex;k++)
{
if(!deleted[k]&&minimum>G[k][i])
{
prev[i]=k+1;
minimum=G[k][i];
}
}
if(minimum==NO_EDGE)
{
throw 1;
}
if (u_find(prev[i]-1) == u_find(i)) {
doCycle(prev[i]-1,i, cost);
cycle = true;
break;
}
else
{
u_union(i,prev[i]-1);
}
}
} while (cycle);
for (int i = 1; i < nVertex; i++) {
if(!deleted[i])
{
cost+=G[prev[i]-1][i];
//cout<<"from "<<(prev[i]-1)<<" to "<<i<<" weight:"<<G[prev[i]-1][i]<<endl;
}
}
printf("%.2f\n",cost);
}
}
]]>
证明Q?br /> 首先我们证明若N是素敎ͼ那么{式成立Q对于N=2,q是很明昄。以下证明N>2 的情形?br /> 1Q若N是素敎ͼ那么关于N同余的乘法群G={1,2,3....N-1}
G每个元素都有逆元Q映?f:a -> a^-1 Qf(a)=a^-1 是一个一一映射。现在，d一个元素，它的逆元要么是其它一个元素，或者是它本w?我们假设其中元素x的逆元是它本nQ那么x*x ≡1(mod N) =>(x+1)*(x-1)=K*N,而N是素敎ͼ所以要么x=N-1,要么x=1。也是_除了q两个元素，其它的元素的逆元都是映射到别的元素的。而N>2,是奇敎ͼ所以元素共有N-1个，也就是偶C元素。这P除了1和N-1外剩余的N-3个元素刚好结成两两一?x,y)(逆元是唯一的）使得f(x)=y=x^-1,也就是xy≡1(mod N).
现在把G的元素全部乘hQ让互ؓ逆元的元素组成一寚w?N-1)!=1*(N-1)*(x1*y1)*(x2*y2)...(xk*yk)≡1*(N-1)*1*1...1 (mod N)≡-1(mod N).
q样Q我们证明了一个方向了Q下面我们证明另一个方?br />
2Q若(N-1)! ≡ -1(mod N)成立Q则N是素敎ͼ若不Ӟ?N是和数。则(N-1)!肯定整除N,因ؓN的每个因子p满p>1,p<N?br /> 现在?N-1)!=K1*N.?N-1)! ≡ -1(mod N) => K1*N ≡ -1(mod N),由同余性质知，存在K2使得K1*N+1=K2*N,两边同时除以N得K1+1/N=K2.昄Q这是不可能的，所以若(N-1)! ≡ -1(mod N)成立Q则N是素?br />
证明完毕Q?br />
q里用群的概念能够简化一定的描述Q其实可以完全不用群的概늚Q只不过q样一来，描述更长点，J琐点！
]]>
今天ȝ上看了一?9q的考研试题Q看见该题目(囄)Q?br />
先来定义l点Qؓ了简便，省略set/get)Q?br />
public class Node
{
public int data;
public Node link;
}
我能惛_的两U解法，一个基于递归Q?{
public int data;
public Node link;
}
递归版的思\是Q基于当前结点，如果后一个是倒数WK-1,那么当前l点是所求，若不Ӟq回当前是倒数W几个?br />
public int printRKWithRecur(Node head,int k)
{
if(k==0||head==null||head.link==null)return 0;
if(_recurFind(head.link,k)>=k)return 1;
return 0;
}
private final int _recurFind(Node node, int k) {
if(node.link==null)
{
return 1;
}
int sRet=_recurFind(node.link,k);
if(sRet==k-1)
{
System.out.println("Got:"+node.data);
return k;
}
return sRet+1;
}
{
if(k==0||head==null||head.link==null)return 0;
if(_recurFind(head.link,k)>=k)return 1;
return 0;
}
private final int _recurFind(Node node, int k) {
if(node.link==null)
{
return 1;
}
int sRet=_recurFind(node.link,k);
if(sRet==k-1)
{
System.out.println("Got:"+node.data);
return k;
}
return sRet+1;
}
Ҏ个结点，该算法都只访问一ơ，因此复杂度O(N).
W二解法Q相寚w归来说Q这U方法可以算是消除递归版，而且从某U意义上来说比递归更高效，跟省I间Q递归版实际上是把回溯的数据存在栈上，而版Ҏ是自己存储，且利用数l实C个@环队列，只存储K个元素?
public static class CycleIntQueue
{
int[] datas;
int top=0;
int num=0;
public CycleIntQueue(int n)
{
datas=new int[n];
}
public void push(int i)
{
datas[(top++)%datas.length]=i;
num++;
}
public int numPushed()
{
return num;
}
public int getButtom()
{
return datas[top%datas.length];
}
}
public int printRKWithCycleQueue(Node head,int k)
{
if(k==0||head==null)return 0;
CycleIntQueue queue=new CycleIntQueue(k);
Node cur=head.link;
while(cur!=null)
{
queue.push(cur.data);
cur=cur.link;
}
if(queue.numPushed()<k)return 0;
System.out.println("Got:"+queue.getButtom());
return 1;
}
{
int[] datas;
int top=0;
int num=0;
public CycleIntQueue(int n)
{
datas=new int[n];
}
public void push(int i)
{
datas[(top++)%datas.length]=i;
num++;
}
public int numPushed()
{
return num;
}
public int getButtom()
{
return datas[top%datas.length];
}
}
public int printRKWithCycleQueue(Node head,int k)
{
if(k==0||head==null)return 0;
CycleIntQueue queue=new CycleIntQueue(k);
Node cur=head.link;
while(cur!=null)
{
queue.push(cur.data);
cur=cur.link;
}
if(queue.numPushed()<k)return 0;
System.out.println("Got:"+queue.getButtom());
return 1;
}
本算法，都每个结点也只放一ơ，另外q行一ơ入队操作，该操作复杂度O(1),从而，整个法复杂度仍是O(N).
]]>
2.各位上的数字之和整除7Q?比如34)
3.L位上包含数字7
附我的代码：
void printN(int n)
{
int c=0;
int i=7;
do
{
if(i%7 ==0)
{
printf("%d\n",i);
c++;
}
else
{
int j=i%10;
int k=j;
int s=k;
int p=10;
while(k<i)
{
if(j==7)
{
printf("%d\n",i);
s=0;
c++;
break;
}
else
{
j=((i-k)/p)%10;
s+=j;
k=j*p+k;
p*=10;
}
}
if(s&&s%7==0)
{
printf("%d\n",i);
c++;
}
}
i++;
} while (c<n);
}
{
int c=0;
int i=7;
do
{
if(i%7 ==0)
{
printf("%d\n",i);
c++;
}
else
{
int j=i%10;
int k=j;
int s=k;
int p=10;
while(k<i)
{
if(j==7)
{
printf("%d\n",i);
s=0;
c++;
break;
}
else
{
j=((i-k)/p)%10;
s+=j;
k=j*p+k;
p*=10;
}
}
if(s&&s%7==0)
{
printf("%d\n",i);
c++;
}
}
i++;
} while (c<n);
}
]]>