【UVA 10820】Send a Table(欧拉函数)
Description
When participating in programming contests, you sometimes face the following problem: You know
how to calcutale the output for the given input values, but your algorithm is way too slow to ever
pass the time limit. However hard you try, you just can’t discover the proper break-off conditions that
would bring down the number of iterations to within acceptable limits.
Now if the range of input values is not too big, there is a way out of this. Let your PC rattle for half
an hour and produce a table of answers for all possible input values, encode this table into a program,
submit it to the judge, et voila: Accepted in 0.000 seconds! (Some would argue that this is cheating,
but remember: In love and programming contests everything is permitted).
Faced with this problem during one programming contest, Jimmy decided to apply such a ’technique’.
But however hard he tried, he wasn’t able to squeeze all his pre-calculated values into a program
small enough to pass the judge. The situation looked hopeless, until he discovered the following property
regarding the answers: the answers where calculated from two integers, but whenever the two
input values had a common factor, the answer could be easily derived from the answer for which the
input values were divided by that factor. To put it in other words:
Say Jimmy had to calculate a function Answer(x, y) where x and y are both integers in the range
[1, N]. When he knows Answer(x, y), he can easily derive Answer(k ∗ x, k ∗ y), where k is any integer
from it by applying some simple calculations involving Answer(x, y) and k.
For example if N = 4, he only needs to know the answers for 11 out of the 16 possible input value
combinations: Answer(1, 1), Answer(1, 2), Answer(2, 1), Answer(1, 3), Answer(2, 3), Answer(3, 2),
Answer(3, 1), Answer(1, 4), Answer(3, 4), Answer(4, 3) and Answer(4, 1). The other 5 can be derived
from them (Answer(2, 2), Answer(3, 3) and Answer(4, 4) from Answer(1, 1), Answer(2, 4) from
Answer(1, 2), and Answer(4, 2) from Answer(2, 1)). Note that the function Answer is not symmetric,
so Answer(3, 2) can not be derived from Answer(2, 3).
Now what we want you to do is: for any values of N from 1 upto and including 50000, give the
number of function Jimmy has to pre-calculate.
Input
The input file contains at most 600 lines of inputs. Each line contains an integer less than 50001 which
indicates the value of N. Input is terminated by a line which contains a zero. This line should not be
processed.
Output
For each line of input produce one line of output. This line contains an integer which indicates how
many values Jimmy has to pre-calculate for a certain value of N.
Sample Input
2
5
0
Sample Output
3
19
题解
问小于n,且两元素互素的二元组有多少个,答案为
###参考代码
```C++
#include <queue>
#include <cmath>
#include <cstdio>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ll long long
#define inf 1000000000
#define PI acos(-1)
#define mem(a,x) memset(a,x,sizeof(a))
using namespace std;
ll read(){
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void Out(ll a){
if(a<0) putchar('-'),a=-a;
if(a>=10) Out(a/10);
putchar(a%10+'0');
}
const int N=50005;
int phi[N];
void phi_table(int n){
for(int i=2;i<=n;i++) phi[i]=0;
phi[1]=1;
for(int i=2;i<=n;i++) if(!phi[i]){
for(int j=i;j<=n;j+=i){
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]/i*(i-1);
}
}
}
int ans[N];
int main(){
phi_table(50000);
for(int i=1;i<=50000;i++) ans[i]=ans[i-1]+phi[i];
while(true){
int n=read();
if(!n) break;
Out(2*ans[n]-1);
puts("");
}
return 0;
}
```\]
最新文章
- 以实际的WebGIS例子探讨Nginx的简单配置
- python之路九
- Git 的详细使用
- ZAM 3D 制作简单的3D字幕 流程(一)
- 关于man和help的区别
- 下载和使用 Open XML PowerTools
- hdu 2647 Reward
- Servlet之初识
- CentOS安装Nginx安装详解
- Flask中endpoint的理解
- 一个简单的模板引(han)擎(shu)
- r语言之生成规则序列,规则序列函数及用法
- T-SQL基础(5) - 表表达式
- webpack 3.X学习之Babel配置
- RDIFramework.NET ━ .NET快速信息化系统开发框架 V3.2版本正式发布
- Vue + WebApi 小项目:构造自己的在线 Markdown 笔记本应用
- SpringBoot 集成Apache Kafak 消息队列
- 【二代示波器教程】第15章 FreeRTOS操作系统版本二代示波器实现
- pyqt5界面使用
- error ...项目路径 \node_modules\chromedriver: Command failed.
热门文章
- nginx使用autoindex
- AtCoder Grand Contest 003 E - Sequential operations on Sequence
- 洛谷 P2147 [SDOI2008]洞穴勘测
- 暴力 BestCoder Round #41 1001 ZCC loves straight flush
- 转 OGG Troubleshooting-Database error 1 (ORA-00001: unique constraint ...)
- req.getParameter()无法获取参数(附前端json序列化)
- Oracle及其相关软件历史版本下载地址
- Centos系统安装 phpredis 扩展
- re正则表达式2
- Eclipse 闪退/无法启动/一闪而过打解决办法