So, you want to do a simple "select count(*) from foo", eh? What's to optimize?
Well, the best way to count the number of rows in a table is to use a fast full-index scan. To do that, use the index_ffs(table,index) hint.
Testing this out on one of our own development tables with approximately 5 million rows, I tried this first:
On a side note, be sure to give your indexes and primary keys meaningful names, so you don't have to refer back to them using Oracle's default "sys_xxxx" naming convention, which is both ugly and not as clear.